LeetCode 15. 3Sum

題目：

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],nnA solution set is:n[n [-1, 0, 1],n [-1, -1, 2]n]n

思路：

先把數組排序，用第一個指針跑一遍數組並去重，之後再用另外兩個指針來湊成target-nums[i]. （Sort the array, iterate through the list, and use another two pointers to approach the target.）

代碼如下：

public List<List<Integer>> threeSum(int[] nums) {n List<List<Integer>> res = new ArrayList<>();n Arrays.sort(nums);n for (int i = 0; i + 2 < nums.length; i++) {n if (i > 0 && nums[i] == nums[i - 1]) { // skip same resultn continue;n }n int j = i + 1, k = nums.length - 1; n int target = -nums[i];n while (j < k) {n if (nums[j] + nums[k] == target) {n res.add(Arrays.asList(nums[i], nums[j], nums[k]));n j++;n k--;n while (j < k && nums[j] == nums[j - 1]) j++; // skip same resultn while (j < k && nums[k] == nums[k + 1]) k--; // skip same resultn } else if (nums[j] + nums[k] > target) {n k--;n } else {n j++;n }n }n }n return res;n} n

推薦閱讀：