15. 三数之和

日期：2022/8/8

题目描述：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

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

示例：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

输入：nums = []
输出：[]

输入：nums = [0]
输出：[]

思路：

排序+三指针
先用left(start)指针，遍历第一个数，第一个数一定是负数，所以遍历的结束条件就是nums[start]>0或start<nums.size()-2
定义mid(index) = start+1，right(end)=n-1，while(mid<right)，依次遍历
定义sum=nums[left]+nums[mid]+nums[right]
当sum>0，就代表nums[right]太大了，right--
当sum<0，就代表nums[mid]小了，mid++
当sum==0，就存入ans中，right++,mid--

代码+解析：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int> > ans;
        if(nums.size()<3) return ans;
        sort(nums.begin(),nums.end());

        for(int start=0; start<nums.size()-2;start++){
            if(nums[start]>0) break;
            if(start>0 && nums[start] == nums[start-1]) continue;
            int end=nums.size()-1;
            int index=start+1;
            while(index<end){
                int sum = nums[start]+nums[index]+nums[end];
                if(sum>0)end--;
                else if(sum<0 || (index>start+1 && nums[index] == nums[index-1]))index++;
                else{
                    ans.push_back({nums[start],nums[index],nums[end]});
                    index++;
                    end--;
                } 
            }
        }
        return ans;
    }
};

最后

以上就是舒服大雁最近收集整理的关于LeetCode算法日记：15. 三数之和15. 三数之和的全部内容，更多相关LeetCode算法日记：15.内容请搜索靠谱客的其他文章。