C++ 双指针_squj

题目1：有序数组的平方

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

vector<int> sortedSquares(vector<int>& nums) {
    vector<int> vecRet(nums.size(), 0);
 
    for (int i = 0, j = nums.size() - 1, nop = nums.size() - 1; nop >= 0; ) {
        int squi = nums[i] * nums[i];
        int squj = nums[j] * nums[j];
        if (squi > squj) {
            vecRet[nop--] = squi;
            i++;
        } else {
            vecRet[nop--] = squj;
            j--;
        }
    }
        
    return vecRet;
}

题目2：轮转数组

给一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。（空间复杂度为 O(1)）

void reverse(vector<int>& nums, int start, int end) {
    for (; start < end; start++, end--) {
        nums[start] ^= nums[end];
	    nums[end] ^= nums[start];
	    nums[start] ^= nums[end];
    }
    return;
}
 
void rotate(vector<int>& nums, int k) {
    /*
    总体思路:整体反转+两边局部反转(空间复杂度O(1))
    如:nums=[1,2,3,4,5,6,7],k=3 -> [5,6,7,1,2,3,4]
    整体反转后:nums=[7,6,5,4,3,2,1]此时[5,6,7]已经位于前面,[4,3,2,1]已经位于后面
    局部反转[0,2]与[3,6]后为[5,6,7,1,2,3,4]就是答案
     */
    int len = nums.size();
    // k可能大于len,要对k进行取余
    k %= len;
    // 不反转以及反转后不变的情形
    if (k == 0 || len == 1) 
        return;
    // 整体反转
    reverse(nums, 0, len - 1);
    // 局部反转
    reverse(nums, 0, k - 1);
    reverse(nums, k, len - 1);
}

题目3：移动零

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

（必须在不复制数组的情况下原地对数组进行操作。）

void moveZeroes(vector<int>& nums) {
    int i = 0, j = 0;
    int len = nums.size();
    for (; i < len; i++) {
        if(0 != nums[i]) {
            nums[j++] = nums[i];
        }
    }
 
    while(j < len) nums[j++] = 0;
}

题目4：两数之和-输入有序数组

给一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

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

vector<int> twoSum(vector<int>& numbers, int target) {
    for (int i = 0, j = numbers.size() - 1; i < j;) {
    int sum = numbers[i] + numbers[j];
        if(sum == target) return vector<int>{i + 1, j + 1};
        else if (sum > target) j--;
        else i++;
    }
    return vector<int>(0);
}