15. 3Sum - Medium

前往題目

照搬一下之前寫的

想法

• 這題很難，覺得應該要是hard
• 解法不複雜，但想法很有挑戰性
• 先排序是因為這樣l和r pointer的位置就很清楚了，l往右一定是維持或是sum變大，r往左一定是維持或是sum變小
• 這個解法是$O(N^2)$

思路

1. Sort it
2. iterate the nums
3. Check if duplicate to the previous number (To prevent redundant check)
4. using 2 pointer, make the initial number fixed so that the problem turns into 2 sum
5. 2 pointers to check the and find sum which is 0
6. When update, just update left pointer until it has a different number from the last one (To prevent redundant), right pointer will be handled by existing logics

Code

public List<List<Integer>> threeSum(int[] nums) {
    /*
    Idea:
        1. Sort it
        2. iterate the nums
        3. Check if duplicate to the previous number
        4. using 2 pointer, make the initial number fixed
            so that the problem turns into 2 sum
        5. 2 pointers to check the and find sum which is 0
        6. When update, just update left pointer
            right pointer will be handled by existing logics
    */

    Arrays.sort(nums); // Sort array to non-decreasing

    List<List<Integer>> res = new LinkedList<List<Integer>>();


    for (int i = 0; i < nums.length - 2; ++i) {
        // Avoid duplicate numbers
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        int l = i + 1, r = nums.length - 1; //Init. 2 pointers, low and high

        // Start to find 2sum
        while (l < r) {
            int threeSum = nums[i] + nums[l] + nums[r]; // Current sum

            if (threeSum > 0) {
                --r;
            } else if (threeSum < 0) {
                ++l;
            } else { // Found 0 condition!
                // Add the result to the array
                res.add(new LinkedList<Integer>(Arrays.asList(nums[i], nums[l], nums[r])));
                ++l;
                while (nums[l] == nums[l - 1] && l < r) {
                    ++l;
                }
            }
        }

    }

    return res;

}

2024/01/07

• 沒想出來，看了解答的思路後寫出來了

2024/01/30

• 大框架寫出來了但缺了一些細節，這個題目的細節蠻容易忽略的，尤其是可能會遇到重複的該怎麼處理