AlphaCamp Leetcode 訓練營 04. Map & Hash Table — 面試應用

課程資訊

此為Alphacamp的Leetcode訓練營，內文僅為個人心得。

練習題：

18. 4Sum

link

題目說明：

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

條件：

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

解法：

官方解

For-loop

For-loop(比上面的方式更慢)

解題概念：
* 0. nums需要先排序
* 1. 總共有四個數字總和要等於target => 找出出第一跟第二個數字的所有組合
* 2. 剩下兩個數字使用twoSum的概念去完成
* 3. 要略過相同的數字，最好是先使用再略過，不然twoSum的範圍會減少

49. Group Anagrams

link

題目說明：

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

條件：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

解法：

347. Top K Frequent Elements

link

題目說明：

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

條件：

• 1 <= nums.length <= 105
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

優化：

Your algorithm’s time complexity must be better than O(n log n), where n is the array's size.

解法：

454. 4Sum II

link

題目說明：

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

條件：

• n == nums1.length
• n == nums2.length
• n == nums3.length
• n == nums4.length
• 1 <= n <= 200
• -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28

解法1：

解法2：