算法题① —— 数组专栏

1. 滑动窗口

1.1 长度最小的子数组

• 力扣：https://leetcode.cn/problems/minimum-size-subarray-sum/description/

int minSubArrayLen(int s, vector<int>& nums) {int result = INT32_MAX; int sum = 0; // 子序列的数值之和int subLength = 0; // 子序列的长度int i = 0;for (int j = 0; j < nums.size(); j++) { sum += nums[j];while (sum >= s) {subLength = j - i + 1;result = result < subLength ? result : subLength;sum -= nums[i++]; }}return result == INT32_MAX ? 0 : result;
}

2. 哈希

2.1 求两数组的交集

• 力扣：https://leetcode.cn/problems/intersection-of-two-arrays/description/

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> result_set; unordered_set<int> nums_set(nums1.begin(), nums1.end());for (int num : nums2) {if (nums_set.find(num) != nums_set.end()) {result_set.insert(num);}}return vector<int>(result_set.begin(), result_set.end());
}

2.2 两数之和

• 力扣：https://leetcode.cn/problems/two-sum/description/

vector<int> twoSum(vector<int>& nums, int target) {unordered_map <int,int> map;for(int i = 0; i < nums.size(); i++) {auto iter = map.find(target - nums[i]); if(iter != map.end()) {return {iter->second, i};}map.insert(pair<int, int>(nums[i], i)); }return {};
}

3. 双指针

3.1 三数之和

• 力扣：https://leetcode.cn/problems/3sum/description/

vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> result;sort(nums.begin(), nums.end());for (int i = 0; i < nums.size(); i++) if (nums[i] > 0) return result;if (i > 0 && nums[i] == nums[i - 1])  continue;int left = i + 1;int right = nums.size() - 1;while (right > left) {if (nums[i] + nums[left] + nums[right] > 0) right--;else if (nums[i] + nums[left] + nums[right] < 0) left++;else {result.push_back(vector<int>{nums[i], nums[left], nums[right]});while (right > left && nums[right] == nums[right - 1]) right--;while (right > left && nums[left] == nums[left + 1]) left++;right--;left++;}}}return result;
}

4. 回溯

4.1 求子集（不包含重复元素）

• 力扣：https://leetcode.cn/problems/subsets/description/

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {result.push_back(path); // 如果结果要包括自己就把push_back放在终止条件上面if (startIndex >= nums.size())  return;for (int i = startIndex; i < nums.size(); i++) {path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}
}
vector<vector<int>> subsets(vector<int>& nums) {backtracking(nums, 0);return result;
}

4.2 求子集（包含重复元素）

• 力扣：https://leetcode.cn/problems/subsets-ii/description/
• 和4.1的区别在于解集中可能会包含重复子集，需要去重（回溯+去重）

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {result.push_back(path);for (int i = startIndex; i < nums.size(); i++) {// 对同一树层使用过的元素进行跳过if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) continue;path.push_back(nums[i]);used[i] = true;backtracking(nums, i + 1, used);used[i] = false;path.pop_back();}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {vector<bool> used(nums.size(), false);sort(nums.begin(), nums.end()); // 去重需要排序backtracking(nums, 0, used);return result;
}

• used[i - 1] == true，说明同一树枝使用过，可以重复选
• used[i - 1] == false，说明同一树层使用过，不可重复选

4.3 递增子序列

• 力扣：https://leetcode.cn/problems/non-decreasing-subsequences/description/
• 特点：同一父节点下同一树层使用过的元素不能重复使用
• 和4.2的区别是：不能排序，只能在原数组基础上搜索

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {if (path.size() > 1) {result.push_back(path);  // 只要path中数组个数大于一个就返回一个结果}unordered_set<int> uset; // 使用set对本层元素进行去重for (int i = startIndex; i < nums.size(); i++) {if ((!path.empty() && nums[i] < path.back()) || uset.find(nums[i]) != uset.end()) continue;uset.insert(nums[i]); // 记录这个元素在本层用过了，本层后面不能再用了path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {backtracking(nums, 0);return result;
}

4.4 全排列（无重复数）

• 力扣：https://leetcode.cn/problems/permutations/description/

vector<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& used) {if (path.size() == nums.size()) {result.push_back(path);return;}for (int i = 0; i < nums.size(); i++) {if (used[i] == true) continue; // path里已经收录的元素，直接跳过used[i] = true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] = false;}
}
vector<vector<int>> permute(vector<int>& nums) {vector<bool> used(nums.size(), false);backtracking(nums, used);return result;
}

4.5 全排列（有重复数）

• 力扣：https://leetcode.cn/problems/permutations-ii/description/

vector<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& used) {if (path.size() == nums.size()) {result.push_back(path);return;}for (int i = 0; i < nums.size(); i++) {if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) continue;if (used[i] == false) {used[i] = true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] = false;}}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end()); // 排序vector<bool> used(nums.size(), false);backtracking(nums, used);return result;
}

• used[i - 1] == true，说明同一树枝使用过，可以重复选
• used[i - 1] == false，说明同一树层使用过，不可重复选

5. 动态规划

5.1 最大子序和（连续子数组）

• 力扣：https://leetcode.cn/problems/maximum-subarray/description/

int maxSubArray(vector<int>& nums) {if (nums.size() == 0) return 0;vector<int> dp(nums.size());dp[0] = nums[0];int result = dp[0];for (int i = 1; i < nums.size(); i++) {dp[i] = max(dp[i - 1] + nums[i], nums[i]); if (dp[i] > result) result = dp[i]; }return result;
}

5.2 最长上升序列（不是连续子数组）

• 力扣：https://leetcode.cn/problems/longest-increasing-subsequence/description/

int lengthOfLIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size();vector<int> dp(nums.size(), 1);int result = 0;for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++)  if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);if (dp[i] > result) result = dp[i]; }return result;
}

5.3 最长连续递增子序列（连续子数组）

• 力扣：https://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/

int findLengthOfLCIS(vector<int>& nums) {if (nums.size() == 0) return 0;int result = 1;vector<int> dp(nums.size() ,1);for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1])  dp[i] = dp[i - 1] + 1;if (dp[i] > result) result = dp[i];}return result;
}

5.4 最长重复子数组（连续子数组）

• 力扣：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/

int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));int result = 0;for (int i = 1; i <= nums1.size(); i++) {for (int j = 1; j <= nums2.size(); j++) {if (nums1[i - 1] == nums2[j - 1])  dp[i][j] = dp[i - 1][j - 1] + 1;if (dp[i][j] > result) result = dp[i][j];}}return result;
}

5.5 最长公共子序列（不是连续子序列）

• 力扣：https://leetcode.cn/problems/longest-common-subsequence/description/

int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));for (int i = 1; i <= text1.size(); i++) {for (int j = 1; j <= text2.size(); j++) {if (text1[i - 1] == text2[j - 1])  dp[i][j] = dp[i - 1][j - 1] + 1;else  dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}return dp[text1.size()][text2.size()];
}