LeetCode Note Java 00015：3Sum

發表於 更新於 分類於 ， ， ， 閱讀次數： Disqus： 文章字數： 290 所需閱讀時間 ≈ 1 分鐘

找出 int Array 中所有三個數相加為 0 的組合。

題目

3Sum Medium

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.

解法

將其中一個數當成 target 即可，剩下就跟 00167：Two Sum II - Input Array Is Sorted 的概念差不多。

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
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums); // 將 nums 由小到大排序
        List<List<Integer>> output = new ArrayList<List<Integer>>();
        for (int i = 0; i < nums.length - 2; i++) { // 因為一次要處理兩個值
          if (i == 0 || i > 0 && nums[i] != nums[i - 1]) { // 避免重複算到一樣的值
            int target = nums[i];
            int l = i + 1, r = nums.length - 1;
            while (l < r) {
              if (target + nums[l] + nums[r] == 0) {
                ArrayList<Integer> outputS = new ArrayList<>();
                outputS.add(target);
                outputS.add(nums[l]);
                outputS.add(nums[r]);
                output.add(outputS);
                while (l < r && nums[l + 1] == nums[l]) { // 避免重複算到一樣的值
                  l++;
                }
                while (l < r && nums[r - 1] == nums[r]) {
                  r--;
                }
                l++;
                r--;
              } else if (target + nums[l] + nums[r] < 0) {
                l++;
              } else {
                r--;
              }
            }
          }
        }
        return output;
    }
}

雖說知道大致解題方向，但寫起來還是一堆障礙，補了一堆條件才通過。

參考資料

leetcode/java/0015-3sum.java