classSolution: deftwoSum(self, nums: List[int], target: int) -> List[int]: n = len(nums) for i inrange(n): for j inrange(i+1, n): if nums[i] + nums[j] == target: return [i, j] return []
哈希表
时间复杂度$O(N)$，空间复杂度$O(N)$，为哈希表的开销
1 2 3 4 5 6 7 8
classSolution: deftwoSum(self, nums: List[int], target: int) -> List[int]: hashtable = dict() for i, num inenumerate(nums): if target - num in hashtable: return [hashtable[target - num], i] hashtable[nums[i]] = i return []
for num in nums_set: if (num - 1) notin nums_set: len = 1
while (num + len) in nums_set: len += 1 maxlen = max(maxlen, len) return maxlen
双指针
移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序
请注意 ，必须在不复制数组的情况下原地对数组进行操作
示例 1:
1 2
输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]
示例 2:
1 2
输入: nums = [0] 输出: [0]
不复制数组只能是直接交换，末尾都是0，头部都是非0值
使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部[快慢指针]
右指针走的更快，以其为循环结束标志
1 2 3 4 5 6 7 8 9 10 11 12
classSolution: defmoveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ n = len(nums) left = right = 0 while right < n: if nums[right] != 0: nums[left], nums[right] = nums[right], nums[left] left += 1 right += 1
盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
classSolution { public: intmaxArea(vector<int>& height){ int left = 0, right = height.size() - 1; int ans = 0; while (left < right) { int water = min(height[left], height[right]) * (right - left); ans = max(ans, water); if (height[left] <= height[right]) left++; else right--; } return ans; } };
三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
classSolution: defthreeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() ans = list() n = len(nums)
for c inrange(n - 2): if c > 0and nums[c] == nums[c - 1]: continue if nums[c] > 0: break l, r = c + 1, n - 1 while l < r: sum = nums[c] + nums[l] + nums[r] ifsum == 0: ans.append([nums[c], nums[l], nums[r]]) l += 1 r -= 1 while l < r and nums[l] == nums[l - 1]: l += 1 while l < r and nums[r] == nums[r + 1]: r -= 1 elifsum < 0: l += 1 else: r -= 1 return ans
classSolution: deflengthOfLongestSubstring(self, s: str) -> int: seen = set() left = 0 max_len = 0 for right inrange(len(s)): while s[right] in seen: seen.remove(s[left]) # 删除直到无s[right] left += 1 seen.add(s[right]) max_len = max(max_len, right - left + 1) return max_len
找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
if prefix_sum - k in mp: ans += mp[prefix_sum - k]
mp[prefix_sum] = mp.get(prefix_sum, 0) + 1
return ans
如果用枚举也有一种方法，起始指针不断向右移动，取起始指针往左计算和，如果累积和匹配则计数+1
但这种方法的复杂度在O(n^2)
1 2 3 4 5 6 7 8 9 10
classSolution: defsubarraySum(self, nums: List[int], k: int) -> int: ans = 0 for start inrange(len(nums)): sum = 0 for end inrange(start, -1, -1): sum += nums[end] ifsum == k: ans += 1 return ans
滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
classSolution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k){ deque<int> dq; int n = nums.size(); // 获取第一个窗口内最大值的索引 for (int i = 0; i < k; i++) { // 没有优先队列的自动排序需要比较后进值与尾端值 while (!dq.empty() && nums[i] >= nums[dq.back()]) { dq.pop_back(); } dq.push_back(i); } vector<int> ans = {nums[dq.front()]}; for (int i = k; i < n; i++) { while (!dq.empty() && nums[i] >= nums[dq.back()]) { dq.pop_back(); } // 保存当前值的索引到队列尾端 dq.push_back(i); // 移出队列头部直到索引在窗口内 while (dq.front() <= i - k) { dq.pop_front(); } ans.push_back(nums[dq.front()]); } return ans; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
classSolution: defmaxSlidingWindow(self, nums: List[int], k: int) -> List[int]: n = len(nums) dq = deque() for i inrange(k): while dq and nums[i] >= nums[dq[-1]]: dq.pop() dq.append(i)
ans = [nums[dq[0]]]
for i inrange(k, n): while dq and nums[i] >= nums[dq[-1]]: dq.pop() dq.append(i) while dq[0] <= i - k: dq.popleft() ans.append(nums[dq[0]]) return ans
 (1).png)
.webp)
