题目
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
解题
方法一：排序+双指针
python写法
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: n = len(nums) if (not nums or n<3): return [] nums.sort() res = [] for i in range(n): if nums[i]>0: return res if (i>0 and nums[i]==nums[i-1]): continue L = i+1 R = n-1 while L<R: if nums[i]+nums[L]+nums[R]==0: res.append([nums[i],nums[L],nums[R]]) while L<R and nums[L]==nums[L+1]: L = L+1 while L<R and nums[R]==nums[R-1]: R = R-1 L = L+1 R = R-1 elif nums[i]+nums[L]+nums[R]<0: L=L+1 else: R=R-1 return res
c++写法
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { int n=nums.size(); if(n<3){ return {}; } sort(nums.begin(),nums.end()); vector<vector<int>> res; for(int i=0;i<n;i++){ if(nums[i]>0){ break; } if(i>0&&nums[i]==nums[i-1]){ continue; } int L=i+1,R=n-1; while(L<R){ int s=nums[i]+nums[L]+nums[R]; if(s==0){ res.push_back({nums[i],nums[L],nums[R]}); while(L<R&&nums[L]==nums[L+1]){ L++; } while(L<R&&nums[R]==nums[R-1]){ R--; } L++; R--; } else if(s<0){ L++; } else{ R--; } } } return res; } };
java写法
class Solution { public List<List<Integer>> threeSum(int[] nums) { int n=nums.length; List<List<Integer>> res=new ArrayList<>(); Arrays.sort(nums); for(int i=0;i<n;i++){ if(nums[i]>0) break; if(i>0&&nums[i]==nums[i-1]) continue; int L=i+1,R=n-1; while(L<R){ int s=nums[i]+nums[L]+nums[R]; if(s==0){ // List<Integer> list=new ArrayList<>(); // list.add(nums[i]); // list.add(nums[L]); // list.add(nums[R]); // res.add(list); res.add(Arrays.asList(nums[i],nums[L],nums[R])); while(L<R&&nums[L]==nums[L+1]){ L++; } while(L<R&&nums[R]==nums[R-1]){ R--; } L++; R--; } else if(s<0){ L++; }else{ R--; } } } return res; } }
