iT邦幫忙

0

[LeetCode 筆記] 15. 3Sum

  • 分享至 

  • xImage
  •  

前言

  這題是一個運用指標的算法,而且是用三個指標來追蹤,運用指標依序掃瞄出題目所要的元素並加起來,使用到了 for、while 兩個迴圈,時間複雜度估達 O(n²),這裡有 JAVA 和 Python 的寫法。

題目

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != ji != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.

給定一個整數陣列 nums,回傳所有的三元組,其中 i != ji != kj != k,且三元組全部加起來等於 0。
注意 這個解決方案必須不含重複的三元組。

題目連結:https://leetcode.com/problems/3sum/

題目限制

3 <= nums.length <= 3000
105 <= nums[i] <= 105

範例

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

思路&筆記

直觀的作法是設定三個指標來掃描,第一個指標先不動,另外兩個指標依序掃描元素,掃描後把全部的元素加起來,判斷裡面的合有沒有等於 0 的,有的話就加入在要輸出的陣列裡,資料結構想到的是把陣列裡的元素個別放進集合裡,再將每一組串列集合放進 HashSet 大集合裡,HashSet 好處是可過濾掉重複的組合。

  • 將 Array 從小到大排序
  • 找出三個數的指標分別表示為 ijk
  • 使用迴圈遍歷,並將 i 做為 nums 的起始點 (指標一)
  • j 則為 i + 1 為起始 (指標二)
  • k 則為 nums.Length - 1 為起始點 (指標三)
  • 首先以 i 為準,從 j 開始掃描到 k 算一輪
  • 並判斷三個指標指向的元素 nums[i] + nums[j] + nums[k] 加起來的合是否為 0 ,是的話會把此組合加進串列集合內
  • 之後讓 j 前進一格,K 後退一格,來排除重複的組合找到下一個組合
  • 由於元素從小排到大,當 sum < target 的話,表示說我們的 j 要繼續往右掃描到一個更大的元素,加起來的合再做判斷
  • 那元素從小排到大,當 sum > target 的話,表示說我們的 k 要繼續往左掃描到一個更小的元素,加起來的合再做判斷

[備註] 使用 HashSet 是為了確保集合裡的資料不重複

簡易示意圖

| -4  | -1  | -1  |  0  |  1  |  2  |
|-----|-----|-----|-----|-----|-----|
|  i  |  j  |     |     |     |  k  |

sum = (-4) + (-1) + 2 = -3
sum < 0,j++
| -4  | -1  | -1  |  0  |  1  |  2  |
|-----|-----|-----|-----|-----|-----|
|  i  |     |  j  |     |     |  k  |

sum = (-4) + (-1) + 2 = -3
sum < 0,j++
| -4  | -1  | -1  |  0  |  1  |  2  |
|-----|-----|-----|-----|-----|-----|
|  i  |     |     |  j  |     |  k  |

sum = (-4) + 0 + 2 = -2
sum < 0,j++
| -4  | -1  | -1  |  0  |  1  |  2  |
|-----|-----|-----|-----|-----|-----|
|  i  |     |     |     |  j  |  k  |

sum = (-4) + 1 + 2 = -1
sum < 0,j++
j == k,回到最新一輪,i++
| -4  | -1  | -1  |  0  |  1  |  2  |
|-----|-----|-----|-----|-----|-----|
|     |  i  |  j  |     |     |  k  |

sum = (-1) + (-1) + 2 = 0,加進集合
j++
k--
| -4  | -1  | -1  |  0  |  1  |  2  |
|-----|-----|-----|-----|-----|-----|
|     |  i  |     |  j  |  k  |     |

sum = (-1) + 0 + 1 = 0,加進集合
j++
k--
j > k,回到最新一輪,i++
| -4  | -1  | -1  |  0  |  1  |  2  |
|-----|-----|-----|-----|-----|-----|
|     |     |  i  |  j  |     |  k  |

i 與上次相同,回到最新一輪,i++
| -4  | -1  | -1  |  0  |  1  |  2  |
|-----|-----|-----|-----|-----|-----|
|     |     |     |  i  |  j  |  k  |

sum = 0 + 1 + 2 = 3

JAVA 實現

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {

        int target = 0; // 目標整數
        Arrays.sort(nums); // 從小到大排序 (原Array)
        Set<List<Integer>> s = new HashSet<>(); // 存元素
        List<List<Integer>> output = new ArrayList<>(); // 輸出用

        for (int i = 0; i < nums.length; i++){
            int j = i + 1; // 指標二
            int k = nums.length - 1; // 指標三
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k]; // 指標全加起來
                if (sum == target) {
					// 將陣列元素轉成集合再加到大集合內
                    // 類似這樣的資料結構 [[1, 2, 3], [2, 3, 4]]
                    s.add(Arrays.asList(nums[i], nums[j], nums[k])); 
                    // 縮小範圍
                    j++; 
                    k--;
                } else if (sum < target) {
                    j++; // 找更大的元素
                } else {
                    k--; // 找更小的元素
                }
            }
        }
        output.addAll(s); // 集合加到陣列裡
        return output;
    }
}

Python 實現

使用了和 Java 一樣的邏輯執行,換成 Python 的寫法。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        target = 0 # 目標整數
        nums.sort() # 從小到大排序 (原Array)
        s = set() # 存元素的集合
        output = [] # 輸出用的陣列
        
        for i in range(len(nums)):
            j = i + 1 # 指標二
            k = len(nums) - 1 # 指標三
            while j < k:
                total = nums[i] + nums[j] + nums[k] # 指標全加起來
                if total == target:
                    s.add((nums[i], nums[j], nums[k])) # 將陣列元素加到集合內
                    j = j+1 # 縮小範圍
                    k = k-1
                elif total < target:
                    j = j+1 # 找更大的元素
                else:
                    k = k-1 # 找更小的元素
        
        output.extend(list(s)) # 添加進陣列
        return output

成績

Language Runtime Memory
Java 706ms 50.8MB
Python 2857ms 20.2MB

(新手上路,如有錯誤請友善告知,感謝)

Blog
https://chris81051.github.io/2023/06/16/LeetCode-15-3Sum-Java-Python/
有分享技術文章、科技新聞、日常生活,歡迎一起討論


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言