### Num1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example: Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

``````    public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i<nums.length;i++){
if(map.containsKey(target-nums[i])){
result[0]=Math.min(i, map.get(target-nums[i]));
result[1]=Math.max(i, map.get(target-nums[i]));
return result;
}
map.put(nums[i], i);
}
return result;
}
``````

### Num11. Container With Most Water

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0).

Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

``````int maxArea(int* heights, int n) {
int water = 0, *i = heights, *j = i + n - 1;
while (i < j) {
int h = *i < *j ? *i : *j;
int w = (j - i) * h;
if (w > water) water = w;
while (*i <= h && i < j) i++;
while (*j <= h && i < j) j--;
}
return water;
}
``````

It’s in C but the main idea is the same. First you start two lines i & j, being the start and the end accordingly. Then using w to record the max volumn of water. Next move i and j toward the middle, keeping moving unless the next line is greater than the current one, do for both i and j. Then calulate min(i,j)*|i-j| compare with w and then w = max(w,min(i,j)*|i-j|) Finally return w. 这道题的主要就是从两边进行搜索，这也是后面很多题目用到的方法。

How this approach works?

Initially we consider the area constituting the exterior most lines. Now, to maximize the area, we need to consider the area between the lines of larger lengths. If we try to move the pointer at the longer line inwards, we won’t gain any increase in area, since it is limited by the shorter line. But moving the shorter line’s pointer could turn out to be beneficial, as per the same argument, despite the reduction in the width. This is done since a relatively longer line obtained by moving the shorter line’s pointer might overcome the reduction in area caused by the width reduction.

### Num15. Three Sum

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] ]

``````public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
int i=0;
while(i<nums.length-2){
if(nums[i]>0) break;
int j= i+1;
int k = nums.length-1;
while(j<k){
int sum = nums[i]+nums[j]+nums[k];
if(sum==0){
ArrayList<Integer> a = new ArrayList();
}
if(sum<=0) while(nums[j]==nums[++j]&&j<k);
if(sum>=0) while(nums[k]==nums[--k]&&j<k);
}
while(nums[i] == nums[++i] && i < nums.length - 2);
}
return result;
}
``````

`````` if(sum<=0) while(nums[j]==nums[++j]&&j<k);
if(sum>=0) while(nums[k]==nums[--k]&&j<k);
``````

### Num16 Three Sum Closest

``````public int threeSumClosest(int[] nums, int target) {
int min = Integer.MAX_VALUE;
Arrays.sort(nums);
int result =0;
int i = 0;
while(i<nums.length-2){
int j = i+1;
int k = nums.length-1;
while(j<k){
int sum = nums[i] + nums[j] + nums[k];
if(min>Math.abs(target-sum)) {
result = sum;
min = Math.abs(target-sum);
}
if(sum<=target) j++;
if(sum>=target) k--;
}
i++;
}
return result;
}
``````

### Num18 Four Sum

The first time win over 100%. Basic idea is using subfunctions for 3sum and 2sum, and keeping throwing all impossible cases. O(n^3) time complexity, O(1) extra space complexity.

``````//数组连4个数都没有，当然返回空
if (nums == null || len < 4)
return res;

//在已经排序的前提下，最小的四个数相加都超过了target，或者最大的四个数加起来都不到target，也没必要算下去了
if (4 * nums[0] > target || 4 * nums[len - 1] < target)
return res;
``````

``````public List<List<Integer>> fourSum(int[] nums, int target) {
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
int len = nums.length;
if (nums == null || len < 4)
return res;

Arrays.sort(nums);

int max = nums[len - 1];
if (4 * nums[0] > target || 4 * max < target)
return res;

int i, z;
for (i = 0; i < len; i++) {
z = nums[i];
if (i > 0 && z == nums[i - 1])// avoid duplicate
continue;
if (z + 3 * max < target) // z is too small
continue;
if (4 * z > target) // z is too large
break;
if (4 * z == target) { // z is the boundary
if (i + 3 < len && nums[i + 3] == z)
break;
}

threeSumForFourSum(nums, target - z, i + 1, len - 1, res, z);
}

return res;
}

/*
* Find all possible distinguished three numbers adding up to the target
* in sorted array nums[] between indices low and high. If there are,
* add all of them into the ArrayList fourSumList, using
*/
public void threeSumForFourSum(int[] nums, int target, int low, int high, ArrayList<List<Integer>> fourSumList,
int z1) {
if (low + 1 >= high)
return;

int max = nums[high];
if (3 * nums[low] > target || 3 * max < target)
return;

int i, z;
for (i = low; i < high - 1; i++) {
z = nums[i];
if (i > low && z == nums[i - 1]) // avoid duplicate
continue;
if (z + 2 * max < target) // z is too small
continue;

if (3 * z > target) // z is too large
break;

if (3 * z == target) { // z is the boundary
if (i + 1 < high && nums[i + 2] == z)
break;
}

twoSumForFourSum(nums, target - z, i + 1, high, fourSumList, z1, z);
}

}

/*
* Find all possible distinguished two numbers adding up to the target
* in sorted array nums[] between indices low and high. If there are,
* add all of them into the ArrayList fourSumList, using
* fourSumList.add(Arrays.asList(z1, z2, the two numbers))
*/
public void twoSumForFourSum(int[] nums, int target, int low, int high, ArrayList<List<Integer>> fourSumList,
int z1, int z2) {

if (low >= high)
return;

if (2 * nums[low] > target || 2 * nums[high] < target)
return;

int i = low, j = high, sum, x;
while (i < j) {
sum = nums[i] + nums[j];
if (sum == target) {

x = nums[i];
while (++i < j && x == nums[i]) // avoid duplicate
;
x = nums[j];
while (i < --j && x == nums[j]) // avoid duplicate
;
}
if (sum < target)
i++;
if (sum > target)
j--;
}
return;
}
``````

### Num26 Remove Duplicates from Sorted Array

``````public int removeDuplicates(int[] nums) {
if (nums.length==0) return 0;
int j = 0;
for(int i =0;i<nums.length;i++){
if(nums[i]!=nums[j]) nums[++j]=nums[i];
}
return j+1;
}
``````

### Num27 Remove Element

``````public int removeElement(int[] nums, int val) {
int j = 0;
for(int i=0;i<nums.length;i++){
if(nums[i]!=val)nums[j++]=nums[i];
}
return j;
}
``````

### Num31 Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column. 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

``````在当前序列中，从尾端往前寻找两个相邻元素，前一个记为first，后一个记为second，并且满足first 小于 second。然后再从尾端寻找另一个元素number，如果满足first 小于number，即将第first个元素与number元素对调，并将second元素之后（包括second）的所有元素颠倒排序，即求出下一个序列
example:
6，3，4，9，8，7，1

``````

``````public int[] nextPermutation(int[] nums) {
int i=nums.length-1;
for(;i>=1;i--){
if(nums[i]>nums[i-1]){
break;
}
}

//swap
if(i!=0){
for(int j = nums.length-1;j>i;j--){
if(nums[j]>nums[i]){
int t = nums[j];
nums[j] = nums[i];
nums[i] = t;
break;
}
}
}

// reverse
int first = i;
int last = nums.length-1;
while(first<last){
int t = nums[first];
nums[first] = nums[last];
nums[last] = t;
first ++;
last --;
}
return nums;
}
``````

### Num33 Search in Rotated Sorted Array

``````public int search(int[] nums, int target) {
int low = 0;
int high = nums.length-1;
int mid = (low+high)/2;

//确定旋转了多少位置
while(low<high){
mid = (low+high)/2;
if(nums[mid]>nums[high]){
low = mid + 1;
}else high = mid;
}
int ro = low;
int realmid;
low = 0;
high = nums.length-1;

//根据旋转的位置二分查找
while(low<=high){
mid=(low+high)/2;
realmid=(mid+ro)%nums.length;
if(nums[realmid]==target)return realmid;
if(nums[realmid]<target)low=mid+1;
else high=mid-1;
}
return -1;
}
``````