末尾有注意点
167. 两数之和 II - 输入有序数组 - 力扣(LeetCode)
双指针:left、right
class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {int right = numbers.size() - 1;int left = 0;while(left < right){int sum = numbers[left] + numbers[right];if(sum == target)return {left+1, right +1};if(sum < target){left++;}else if(sum > target){right--;}}return {-1, -1};}
};
15. 三数之和 - 力扣(LeetCode)
转化成两数之和
class Solution {
public:vector<vector<int>> help(vector<int>& nums, int left, int right, int target, int value){vector<vector<int>>answer;while(left < right){int sum = nums[left] + nums[right];if(sum == target){vector<int> result;result.push_back(value);result.push_back(nums[left]);result.push_back(nums[right]);answer.push_back(result);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 answer;}vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), nums.end());//快排int len = nums.size();vector<vector<int>>answer;vector<vector<int>> result;for(int i = 0; i < len; i++){if(i >0 && nums[i] == nums[i-1]) {continue;}result = help(nums, i+1, len-1, -nums[i], nums[i]);answer.insert(answer.end(), result.begin(), result.end());}return answer;}
};
注意:
如果写成(nums[i] == nums[i-1] && i >0)会报错,因为先执行的nums[i-1],i-1如果= -1就会报错,i>0放前面会先执行;