leetcode--双指针

这周是我在leetcode上刷题的第一周，然后我就把和第一题同一系列的题差不多都做了，我记得我们上高三的时候我们老师就是一个系列一个系列的出题，我觉得编程题和数学题并没有本质上的区别，所以我们也应该这么刷嘛。

题目类型

Two Sum II

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

Your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.
Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

3Sum Closest

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

这几道题都是有共同点的：
1.他们用的共同的数据结构都是数组
2.他们的要求都是在数组中找到某个或某几个符合要求的元素
3.他们都会给一个目标值，通过某个目标值来找到那几个元素
在数组中找到某个值我就想到了二分查找，二分查找的代码是这样的：

//非递归
public static int binarySearch(int[] arr, int start, int end, int target){
    int result = -1;

    while (start <= end){
        int mid = start + (end - start)/2;    //防止溢位
        if (arr[mid] > target)
            end = mid - 1;
        else if (arr[mid] < target)
            start = mid + 1;
        else {
            result = mid ;  
            break;
        }
    }

    return result;

}

我们先来做Two Sum II，因为这个题最简单嘛，并且这些题都是一个系列的，会一道应该就都会了。
那么我们就可以假设是不是对这个代码改一改就能得到题的答案呢？
我们可以在start和end两个指针上做点处理，代码就成这样了：

public int[] twoSum(int[] nums, int target) {
        for (int start = 0, end = nums.length - 1; start < end && end < nums.length; ) {
            if (nums[start] + nums[end] > target)
                end--;
            else if (nums[start] + nums[end] < target)
                i++;
            else return new int[] {start + 1, end + 1};
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

然后跑一下：

第一个打败100%.png

emmmm到这个份上应该契合题意了吧，然后对这类题应该就是用两个指针在数组上遍历才叫双指针的吧。