Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
三数之和,重点是如何遍历后去除重复的数组。 首先对数组进行排序。 遍历数组,三个数中最小的数字为nums[i]。此时需要去除重复的nums[i]。如重复则继续下一次循环。 此时设置双指针left和right,分别在nums[i]右侧的子数组的首尾。
当nums[i] + nums[left] + nums[right] > 0时,后两个数的和需要减小,right指针向左移动。
当nums[i] + nums[left] + nums[right] < 0时,后两个数的和需要增大,left指针向右移动。
当nums[i] + nums[left] + nums[right] = 0时,找到一个组合。此时需要去除重复的nums[left]和nums[right]。如重复则更新left或right的指针。
将组合添加到返回列表。
最后返回列表。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution { public List<List<Integer>> threeSum (int [] nums) { List<List<Integer>> ans = new ArrayList (); Arrays.sort(nums); for (int i = 0 ; i < nums.length; i++){ int left = i+1 ; int right = nums.length-1 ; if (i>0 && nums[i] == nums[i-1 ]){ continue ; } while (left < right){ if (nums[i]+nums[left]+nums[right]==0 ){ while (left+1 < nums.length && nums[left] == nums[left+1 ]){ left++; } while (right-1 > i && nums[right] == nums[right-1 ]){ right--; } List<Integer> list = new ArrayList (); list.add(nums[i]); list.add(nums[left]); list.add(nums[right]); ans.add(list); left++; right--; } else if (nums[i]+nums[left]+nums[right]>0 ){ right--; } else { left++; } } } return ans; } }