給定一個包含 n 個整數的數組?nums，判斷?nums?中是否存在三個元素 a，b，c ，使得?a + b + c = 0 ？找出所有滿足條件且不重復的三元組。

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

例如, 給定數組 nums = [-1, 0, 1, 2, -1, -4]，

滿足要求的三元組集合為：
[
? [-1, 0, 1],
? [-1, -1, 2]
]

思路：雙指針法

要求的是a+b+c=0

1.首先可以先排序（O(nlogn)），這樣保證數組有序之后可以利用大小關系判斷。

2.設置兩個指針start、end，分別從左邊以及右邊向中間遍歷，如果找到a+b+c==0，那么可以將這個答案加入到答案集里 如果a+b+c<0，此時固定的是c，說明a+b太小了，因此start+=1；如果a+b+c>0，此時a+b過大，因此end-=1

3.去重，這一步則是利用了有序性，如果兩個數相同，那他們在數組的位置一定是相鄰的（連著幾個數相同也是可能的），因此 去重的操作就能簡單遍歷一下相鄰的是否相同即可。由于數組有序性使得去重這一步很簡單，因此也可以看出第一步的作用。

提交的代碼：

class Solution {
? ? public List<List<Integer>> threeSum(int[] nums) {
? ? ? ? Arrays.sort(nums);
? ? ? ? int i,start=1,end=nums.length-1;
? ? ? ? List<List<Integer>> result = new ArrayList<List<Integer>>();
? ? ? ? for(i=0;i<nums.length-2;i++)
? ? ? ? {
? ? ? ? ? ? if(i > 0 && nums[i] == nums[i-1]) continue; //去重
? ? ? ? ? ? start=i+1;
? ? ? ? ? ? end=nums.length-1;
? ? ? ? ? ? while(start<end)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(nums[i]+nums[start]+nums[end]>0)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? end--;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else if(nums[i]+nums[start]+nums[end]<0)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? start++;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? List<Integer> list = new ArrayList<Integer>();
? ? ? ? ? ? ? ? ? ? list.add(nums[i]);
? ? ? ? ? ? ? ? ? ? list.add(nums[start]);
? ? ? ? ? ? ? ? ? ? list.add(nums[end]);
? ? ? ? ? ? ? ? ? ? result.add(list);
? ? ? ? ? ? ? ? ? ? while (start<end && nums[start] == nums[start+1]) start++; // 去重
? ? ? ? ? ? ? ? ? ? while (start<end && nums[end] == nums[end-1]) end--; // 去重
? ? ? ? ? ? ? ? ? ? start++;
? ? ? ? ? ? ? ? ? ? end--;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return result;
? ? }
}

總結

以上是生活随笔為你收集整理的Leetcode--15. 三数之和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。