Leetcode-15-三数之和为0

题目链接


题目描述

给你 n 个整数的数组 nums,判断是否存在三个元素 a,b,c ,
使得 a + b + c = 0 ?
请你找出所有和为 0 且不重复的三元组。

注意: 答案中不可以包含重复的三元组。


思路

  1. 假设不是找三个元素,而是两个元素。
    首先要确定一个元素,至少要把所有元素遍历一遍,是O(n)。
    其次,找到另一个符合的元素的最优复杂度是O(logn),合起来的复杂度是O(nlogn)。
    关键是如何避免重复,可以先把数组排序,确定第一个元素时,遇到重复的直接跳过。
    第一个元素不重复,那么找到的第二个元素一定也不重复。

  2. 那么考虑三个元素时,排序+双指针
    从后往前遍历。
    若 nums[i]>0,因已排序,后面不可能有三个数加和等于0,直接返回结果。
    对于重复元素:跳过,避免出现重复解。
    令左指针为L=i+1,右指针R=n-1,当 L<R 时,执行循环:
    当 nums[i]+nums[L]+nums[R]==0,记录答案,并更新左指针,同时判断是否重复。
    若和大于 0,说明 nums[R]太大,R 左移
    若和小于 0,说明 nums[L]太小,L 右移
    时间复杂度为O(n^2)


C++方法

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int pL, pR, T, L, R;
        int len = nums.size();
        vector<vector<int>> ans;
        for (int i = 0; i < len; i++) {
            if (i != 0 && nums[i] == nums[i-1])
                continue;
            T = nums[i];
            if (T > 0)
                break;
            pL = i+1, pR = len-1;
            while(pL < pR) {
                L = nums[pL], R = nums[pR];
                if (T+L+R == 0) {
                    ans.push_back({L,T,R});
                    pL ++;
                    while (pL<pR && nums[pL-1] == nums[pL])
                        pL++;
                }
                else if (T+L+R < 0)
                    pL ++;
                else if (T+L+R > 0)
                    pR --;
            }
        }
        return ans;
    }
};
上一篇:Zynq——PL_BRAM_PS数据传输


下一篇:oracle PL/SQL块匿名块和函数的练习