iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 4
1
Software Development

從LeetCode學演算法系列 第 4

[Day 4] 從LeetCode學演算法 - 0015. 3Sum (Medium)

目標:
這題主要目的在於練習Two Pointer類型的問題應用。

原題:

Question:
Given an array nums of n integers, are there elements a, b, c in numssuch 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.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

分析/解題:
題目要求從陣列中找出所有數組a, b, c,
使得三者相加為0,且不能重覆。

老話一句,請記得問有沒有排序XD~
以暴力法解本題的話,會發現每次取三個做組合,
顯然會得到一個O(N³)的時間複雜度的解。
那麼,嘗試排序看看能得到比較好的解嗎?
我們先拿題目的例子來看看,排序過後為
[-4, -1, -1, 0, 1, 2]
按順序排列會有什麼好處呢?
假設我們先固定最左邊的-4為a(因為要組合,我們可以令a<=b<=c),
那麼b+c必須等於4,這邊使用一個簡單的技巧,
先將b指定給-1的位置,c指定給2的位置,
兩者相加等於1,表示應該要取更大的值才有機會讓和等於4,
於是我們可以將b的位置向右移一格(這裡是重覆的所以可以跳過),
再次檢查和目標的大小比較。

那麼很容易可以發現一件事情:
當現在的值比目標值大時,表示應該要取更小的值
只有將c往左移動才有可能達到。
反之,
當現在的值比目標值小時,表示應該要取更大的值,
只有將b往右移動才有可能達到。
因此,在固定a值的時候,只要將後面的數按照上面的方法,
一次移動一格的掃過一遍,就可以得到這個a值所可以成立的組合。

所以最終我們只要將a從0~len(nums)-3按順序跑過一遍,
將中間符合的組合都放進list中,即可得到答案。

重覆性的部分,只要記得檢查前一個和這一個用的數字是否相同即可避免。

上述的做法,由於使用到兩個指標(指針),並透過移動它們來達到掃描陣列的目的,我們通常稱這樣的解法為Two Pointer,是蠻常用的技巧。
時間複雜度的部分,排序的一般狀況是O(NlogN),
而a的長度是O(N),每次都要掃完其後的長度,掃描部分即為O(N²),
所以總體的時間複雜度為O(N²)。

Java:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new LinkedList<>(); 
        for (int i = 0; i < nums.length-2; i++) {
            if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
                int j = i + 1, k = nums.length - 1, target = 0 - nums[i];
                while (j < k) {
                    if (nums[j] + nums[k] == target) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                        while (j < k && nums[j] == nums[j + 1]) j++;
                        while (j < k && nums[k] == nums[k - 1]) k--;
                        j++; k--;
                    } else if (nums[j] + nums[k] < target) ++j;
                    else --k;
               }
            }
        }
        return res;
    }
}

Python:
Python的部分提供了另一個的思路,
這是由 RouRouKerr在討論區所提出的解法,這邊是改成Python3版本。
他的想法是,在固定第一個數v的狀況,那當其中一個數為x,
另一個數只能是-v-x(因為加總要等於0)。
故每次將對應的互補數加入到dict中,
我們只要從頭到尾檢查,即可得到所有的正確組合。
這個想法跟前面Two Sum的解法概念是一樣的。
(對應到Java版本的解法也附在註解處)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) < 3:
            return []
        nums.sort()
        res = set()
        for i, v in enumerate(nums[:-2]):
            if i >= 1 and v == nums[i-1]:
                continue
            d = {}
            for x in nums[i+1:]:
                if x not in d:
                    d[-v-x] = 1
                else:
                    res.add((v, -v-x, x))
        return list(res)

'''class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        for i in range(len(nums) - 2):
            if i == 0 or (i > 0 and nums[i] != nums[i-1]):
                j, k, target = i + 1, len(nums) - 1, 0 - nums[i]
                while j < k:
                    if nums[j] + nums[k] == target:
                        res.append([nums[i], nums[j], nums[k]])
                        while j < k and nums[j] == nums[j+1]:
                            j += 1
                        while j < k and nums[k] == nums[k-1]:
                            k -= 1
                        j += 1
                        k -= 1
                    elif nums[j] + nums[k] < target:
                        j += 1
                    else:
                        k -= 1
        return res
'''

面試實際可能會遇到的問題:
「(Python)前面不檢查的話後面你怎麼處理重覆?」(用set)
「假設目標不是0的話?」(方法應該是一樣的)
「(Python)dictionary的部分使用set代替會比較快嗎?」(實測過會變慢XD)
「(Java)如果可以改變input/output的變數形態的話,你會希望改動什麼?」
(改output,因為輸出應該固定會是3元組的組合(長度必然是3),
那大可以使用List<int[]>,用List<List>其實較不理想)

只要掌握了Two Pointers的概念,很多題目其實可以在排序後輕鬆解決,
但記得注意有些題目可以比O(NlogN)快的話,排序會提高時間複雜度歐!

從LeetCode學演算法,我們下次見囉,掰~

下篇預告:
0021. Merge Two Sorted Lists (Easy)


上一篇
[Day 3] 從LeetCode學演算法 - 0014. Longest Common Prefix (Easy)
下一篇
[Day 5] 從LeetCode學演算法 - 0021. Merge Two Sorted Lists (Easy)
系列文
從LeetCode學演算法30

尚未有邦友留言

立即登入留言