1. 两数之和

直接利用hashmap存储值和对于索引，利用target-nums[i]去哈希表里找对应数值。返回下标。

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> mp;vector<int> res;for (int i = 0; i < nums.size(); ++i) {if (mp.find(target - nums[i]) != mp.end()) {res.push_back(i);res.push_back(mp[target - nums[i]]);}mp[nums[i]] = i;}return res;}
};

15. 三数之和

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;if (nums.empty() || nums.size() < 3) {return res;} sort(nums.begin(), nums.end());for (int i = 0; i < nums.size(); ++i) {if (nums[i] > 0) {break;}if (i > 0 && nums[i] == nums[i-1]) {continue;}int left = i + 1;int right = nums.size() - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (sum > 0) {right--;} else if (sum < 0) {left++;} else {res.push_back({nums[i], nums[left], nums[right]});while (left < right && nums[left] == nums[left+1]) {left++;}while (left < right && nums[right] == nums[right-1]) {right--;}left++;right--;}}}return res;}
};

16. 最接近的三数之和

排序+双指针

class Solution {
public:int threeSumClosest(vector<int>& nums, int target) {sort(nums.begin(), nums.end());long res = INT_MAX;for (int i = 0; i < nums.size(); ++i) {int left = i + 1;int right = nums.size() - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (abs(target - sum) < abs(target - res)) {res = sum;}if (sum > target) {right--;} else if (sum < target) {left++;} else {return res;}}}return res;}
};

 18. 四数之和

本题与「15. 三数之和」相似，解法也相似。

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> quadruplets;if (nums.size() < 4) {return quadruplets;}sort(nums.begin(), nums.end());int length = nums.size();for (int i = 0; i < length - 3; i++) {if (i > 0 && nums[i] == nums[i - 1]) {continue;}if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {break;}if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {continue;}for (int j = i + 1; j < length - 2; j++) {if (j > i + 1 && nums[j] == nums[j - 1]) {continue;}if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {break;}if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {continue;}int left = j + 1, right = length - 1;while (left < right) {long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];if (sum == target) {quadruplets.push_back({nums[i], nums[j], nums[left], nums[right]});while (left < right && nums[left] == nums[left + 1]) {left++;}left++;while (left < right && nums[right] == nums[right - 1]) {right--;}right--;} else if (sum < target) {left++;} else {right--;}}}}return quadruplets;}
};

560. 和为 K 的子数组

使用前缀和

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int, int> mp;mp[0] = 1;int sum = 0, count = 0;for (int i = 0; i < nums.size(); ++i) {sum += nums[i];if (mp.find(sum - k) != mp.end()) {count += mp[sum - k];}mp[sum]++;}return count;}
};

53. 最大子数组和

动态规划

class Solution {
public:int maxSubArray(vector<int>& nums) {vector<int> dp(nums.size());dp[0] = nums[0];for (int i = 1; i < nums.size(); ++i) {dp[i] = max(dp[i-1] + nums[i], nums[i]);}int res = nums[0];for (int i = 1; i < nums.size(); ++i) {res = max(res, dp[i]);}return res;}
};

class Solution {
public:int maxSubArray(vector<int>& nums) {int pre = 0;int res = nums[0];for (int i = 0; i < nums.size(); ++i) {pre = max(pre + nums[i], nums[i]);res = max(res, pre);}return res;}
};