LeetCode算法题解——双指针2

这里介绍双指针在数组中的第二类题型：两端夹击。

第五题

977. 有序数组的平方

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

示例1:

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

思路

因为是排序每个数字的平方，根据二次函数图像y=x^2开口向上可得，最大值在两端，最小值在中间。所以，最左和最右进行比较，两端夹击，看谁的平方值更大。

代码

class Solution {public int[] sortedSquares(int[] nums) {int n = nums.length;int[] result = new int[n];int l = 0;int r = n - 1;int k = n - 1;while(l <= r){if(nums[l] * nums[l] > nums[r] * nums[r]){result[k] = nums[l] * nums[l];l++;k--;}else{result[k] = nums[r] * nums[r];r--;k--;}}return result;}
}

第六题

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

题目描述:
给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

示例1:

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

思路

可以先考虑边界情况。升序数组中任意两个元素求和，最小为nums[0]+nums[1]，最大为nums[n-2]+nums[n-1]。target的范围一定在这两者之间，否则找不到答案。所以，我们可以两端夹击，一直手抓nums[0]，另一只手抓nums[n-1]。如果是最小的情况，那么让nums[n-1]向nums[1]靠拢；如果是最大的情况，那么让nums[1]向nums[n-2]靠拢。

代码

class Solution {public int[] twoSum(int[] numbers, int target) {int l = 0, r = numbers.length - 1;int[] result = new int[]{0, 0};while(l < r){int sum = numbers[l] + numbers[r];if(sum == target){result[0] = l + 1;result[1] = r + 1;break;}else if(sum < target){l++;}else{r--;}}return result;}
}

第七题

633. 平方数之和

题目描述:
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a^2 + b^2 = c 。

示例1:

输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5

思路

上一题是两个数的和是否为target，这道题是两个数的平方和是否为target。一样的思路，考虑最大最小值。若两个数的平方和为target，则最小为0，最大为target的平方根。同样的，两端夹击。

代码

class Solution {public boolean judgeSquareSum(int c) {long l = 0;long r = (long) Math.sqrt(c);while(l <= r){long m = l * l + r * r;if(m == c){return true;}else if(m < c){l++;}else{r--;}}return false;}
}

下一篇博客LeetCode算法题解——双指针3中，我将分享LeetCode中关于字符串的双指针问题。

参考：

Leetcode 题解 - 双指针