刷题笔记 day6

力扣 57 和为s的两个整数

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int>  v;int i =0 , j = nums.size()-1;while(i < j){if(nums[i]+ nums[j] > target){--j;}else if(nums[i] + nums[j] < target){++i;}else{v.push_back(nums[i]);v.push_back(nums[j]);break;}}return v;}
};

 对于一个递增排序的数组，我们可以使用双指针；

定义指针 left 指向数组最左端元素 ， 定义指针 right 指向数组最右端元素；

当 nums[left] + nums[right]  >  target 时，右移指针right;

当 nums[left] + nums[right]  < target 时，左移指针left;

当 nums[left] + nums[right]  ==  target 时，输出结果。

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int>  v;int i =0 , j = nums.size()-1;while(i < j){if(nums[i]+ nums[j] > target){--j;}else if(nums[i] + nums[j] < target){++i;}else{v.push_back(nums[i]);v.push_back(nums[j]);break;}}return v;}
};

力扣 15 三数之和

 

思路：1. 先给数组排序（升序）

2.  固定 最右端的数 a；

3.  将数a左边的区间两端定义双指针 left 和 right , 求这三个数（a, nums[left],nums[right）之和是否等于0； 大于0 ， 右移right ; 小于 0 ，左移 left.

由于输出结果中不能含有重复性元素，所以在算法过程中要去重。

1.  找到一种结果后 ， left 和 right 要跳过 重复元素。

2.  使用完一次双指针后， 下一次固定的数不能重复。

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {//先排序sort(nums.begin(),nums.end());vector<vector<int>> v;int c = nums.size()-1;while( c>=2){if(nums[c] < 0) // 如果最大的数小于0，那么将不存在三个数之和为零的情况{return v;}int left = 0, right = c-1;while(left < right){if(nums[left]+nums[right]+nums[c] >0){--right;}else if(nums[left]+nums[right]+nums[c] <0){++left;}else{v.push_back({nums[left],nums[right],nums[c]});++left;while(left < right&& nums[left] == nums[left-1])  //left不能越界{++left;}--right;while(left < right && nums[right] == nums[right+1])//right不能越界{--right;}}}--c;while(c >= 2 && nums[c] == nums[c+1]) //c不能越界{--c;}}return v;}
};

 力扣  18 四数之和

 思路：

   这道题的解题方法和上一道题一样。

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(),nums.end());vector<vector<int>> v;int c = nums.size()-1;while(c>=3){int  b = c-1;while(b>=2){int left = 0 , right  = b-1;while(left < right){long long sum =(long long) nums[left] + nums[right] + nums[b] + nums[c];if(sum > target){--right;}else if(sum < target){++left;}else{v.push_back({nums[left],nums[right],nums[b],nums[c]});++left;while(left < right && nums[left] == nums[left-1]){++left;}--right;while(left < right && nums[right] == nums[right +1]){--right;}}}--b;while(b >=2 && nums[b] == nums[b+1]){--b;}}--c;while(c >=3 && nums[c] == nums[c+1]){--c;}}return v;}
};