這周是我在leetcode上刷題的第一周左腔，然后我就把和第一題同一系列的題差不多都做了，我記得我們上高三的時(shí)候我們老師就是一個(gè)系列一個(gè)系列的出題麦备，我覺得編程題和數(shù)學(xué)題并沒有本質(zhì)上的區(qū)別逃默，所以我們也應(yīng)該這么刷嘛虾宇。
題目類型
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).
這幾道題都是有共同點(diǎn)的：
1.他們用的共同的數(shù)據(jù)結(jié)構(gòu)都是數(shù)組
2.他們的要求都是在數(shù)組中找到某個(gè)或某幾個(gè)符合要求的元素
3.他們都會(huì)給一個(gè)目標(biāo)值搓彻，通過某個(gè)目標(biāo)值來找到那幾個(gè)元素
在數(shù)組中找到某個(gè)值我就想到了二分查找，二分查找的代碼是這樣的：
//非遞歸
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嘱朽，因?yàn)檫@個(gè)題最簡(jiǎn)單嘛旭贬，并且這些題都是一個(gè)系列的，會(huì)一道應(yīng)該就都會(huì)了搪泳。
那么我們就可以假設(shè)是不是對(duì)這個(gè)代碼改一改就能得到題的答案呢稀轨？
我們可以在start和end兩個(gè)指針上做點(diǎn)處理，代碼就成這樣了：
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");
}
}
然后跑一下：
emmmm到這個(gè)份上應(yīng)該契合題意了吧岸军，然后對(duì)這類題應(yīng)該就是用兩個(gè)指針在數(shù)組上遍歷才叫雙指針的吧奋刽。
