双指针C++

双指针夹逼定理

977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序

进阶：

请你设计时间复杂度为 O(n) 的算法解决本问题

题解

//原题本来就是排序的，只不过有负数；
//kk是从后往前的下标；
//从前往后插
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
    vector<int> n1(nums.size());
    int rr=nums.size()-1;
    int ll=0; int kk=nums.size()-1;
while(ll<=rr)
{
if(abs(nums[ll])>abs(nums[rr])){n1[kk]=(nums[ll]*nums[ll]);ll++;kk--;}
if(abs(nums[ll])<=abs(nums[rr])){n1[kk]=(nums[rr]*nums[rr]);rr--;kk--;}
}
    return n1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

题解

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
int n=nums.size();
int a=0;//aa是从前往后的下标；
for(int i=0;i<n;i++)//先把非0元素移向前，用a 记录
    if(nums[i]!=0)
      nums[a++]=nums[i];
for(int i=a;i<n;i++)//后面都为0
    nums[i]=0;
}
};
1
2
3
4
5
6
7
8
9
10
11
12

167. 两数之和 II - 输入有序数组

给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]

提示：

2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 非递减顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案

题解

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
      int n=numbers.size();
      int a=0,b=n-1;
      while(a<b)
      {
        if(numbers[a]+numbers[b]>target)        b--;
        else if(numbers[a]+numbers[b]==target) return vector<int>{a+1,b+1};
        else                                    a++;
      }
          return vector<int>{-1, -1};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

344. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = [“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]
示例 2：

输入