数组

练习：Three Sum（求三数之和）

思路：

先将数组排序。
将Three Sum转换为Two Sum来做。
将num[i]的相反数即-num[i]作为target，然后从i+1到len(num)-1的数组元素中寻找两个数使它们的和为-num[i]。下标i的范围是从0到len(num)-3。
过程中注意去重。（否则会报错：Time Limit Exceeded）
时间复杂度为O(N^2)。

class Solution:
    def threeSum(self, nums):
        nums.sort()
        res = []
        for i in range(len(nums)-2):
            if i == 0 or nums[i] > nums[i-1]:
                left = i + 1
                right = len(nums) - 1
                while left < right:
                    if nums[left] + nums[right] == -nums[i]:
                        res.append([nums[i], nums[left], nums[right]])
                        left += 1
                        right -= 1
                        while left < right and nums[left] == nums[left-1]: # 去重
                            left += 1
                        while left < right and nums[right] == nums[right+1]: # 去重
                            right -= 1
                    elif nums[left] + nums[right] < -nums[i]:
                        while left < right:
                            left += 1
                            if nums[left] > nums[left-1]: # 去重
                                break
                    else:
                        while left < right:
                            right -= 1
                            if nums[right] < nums[right+1]: # 去重
                                break
        return res

Majority Element（求众数）

思路：
按列表去重后的元素依次计数、比较。

class Solution:
    def majorityElement(self, nums):
        nums_set = set(nums)
        compare_count = int(len(nums)/2)
        for num in nums_set:
            count = nums.count(num)
            if count > compare_count:
                return num

Missing Positive（求缺失的第一个正数）

要求：时间复杂度在O(n)内，使用恒定的额外空间。

思路：
使用字典hash求解。

class Solution:
    def firstMissingPositive(self, nums):
        # 处理空值: []对应的结果为1
        if len(nums) == 0:
            return 1
        
        # 构建用于hash的字典
        hash_dict = {}
        for num in nums:
            # 只有正数参与hash
            if num > 0:
                hash_dict[num] = 1
        
        # 处理空值: 字典为空, 对应的结果为1
        if len(hash_dict) == 0:
            return 1
        
        # 遍历[1, max(hash_dict.keys())+1], 字典中最大的数+1
        # 如果前面有空的, 则在最大的数之前即可返回
        # 否则, 在最大的数+1处返回
        for num in range(1, max(hash_dict.keys())+2):
            if num not in hash_dict.keys():
                return num

链表

练习：Linked List Cycle I（环形链表）

思路：快慢指针

class Solution(object):
    def hasCycle(self, head):
        slow = fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                return True
        return False

Merge k Sorted Lists（合并 k 个排序链表）

思路：小根堆保存值和索引

class Solution:
    def mergeKLists(self, lists):
        head = ListNode(-1)
        move = head
        heap = []
        heapq.heapify(heap)
        [heapq.heappush(heap, (l.val, i)) for i, l in enumerate(lists) if l]
        while heap:
            curVal, curIndex = heapq.heappop(heap)
            curHead = lists[curIndex]
            curNext = curHead.next
            move.next = curHead
            curHead.next = None
            move = curHead
            curHead = curNext
            if curHead:
                lists[curIndex] = curHead
                heapq.heappush(heap, (curHead.val, curIndex))
        return head.next

[数据结构]数组、链表

数组

练习：Three Sum（求三数之和）

Majority Element（求众数）

Missing Positive（求缺失的第一个正数）

链表

练习：Linked List Cycle I（环形链表）

Merge k Sorted Lists（合并 k 个排序链表）

相关链接