1.Move Zeroes

Given an array nums, write a function to move all 0's to the 
end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

题目要求：在不使用额外的数组的条件下将数组中的0全部移到右边
我最开始的做法如下：

class Solution {
    public void moveZeroes(int[] nums) {
        int len = nums.length;
        for (int i = len - 1; i >= 0; i--) {
            if (nums[i] == 0) {
                for (int j = i; j < len - 1; j++) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
    }
}

每当遇到0就做一次移位，将0移到最右边。这个做法的缺点在于耗时。
改进后的代码：

public class Solution1 {
    public void moveZeroes(int[] nums) {
        int index = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[++index] = nums[i];
            }
        }
        for (int i = index + 1; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

利用一个额外参数Index来做数组的变换，在最后再添加0即可

2.Find All Numbers Disappeared in an Array

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array)
, some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? 
You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

这道题是用很常规的数组的做法，该做法可以解决一部分的题目：用另一个数组记录每个数出现的次数

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<>();
        int temp[] = new int[nums.length+1];
        for (int i = 0; i < nums.length; i++) {
            temp[nums[i]]++;
        }
        for (int i = 1; i < temp.length; i++) {
            if (temp[i] == 0)
                result.add(i);
        }
        return result;
    }
}

3.Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the 
price of a given stock on day i.

If you were only permitted to complete at most one transaction 
(i.e., buy one and sell one share of the stock), design an algorithm to find the 
maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

3.1(集合排序)

这道题我开始利用List集合的排序去做，结果超时
超时代码如下(权当提供一种思路了)：

class Solution {
    //使用Map出现很大的失误：map中不能有相同的key，但是本题当 input= [1,4,1,4,3,1]时出现问题，
    // 注意用map + sort 的时候一定要注意是否会出现相同的key这一问题
    List<Bianhao> list = new ArrayList<>();
    public int maxProfit(int[] prices) {
        for (int i = 0; i < prices.length; i++) {
            list.add(new Bianhao(prices[i],i));
        }
        Collections.sort(list);
        Arrays.sort(prices);
        return solve(prices, 0, prices.length - 1);
    }

    public int solve(int[] prices, int start, int end) {
        if (start >= end) return 0;
        //如果最大和最小刚好满足条件，就是最简单的情况
        if (list.get(start).getKey()<list.get(end).getKey()) {
            return prices[end] - prices[start];
        }
        return Math.max(solve(prices, start + 1, end), solve(prices, start, end - 1));
    }
}

class Bianhao implements Comparable<Bianhao>{
    private Integer value;
    private int key;

    public Bianhao(Integer value, int key) {
        this.value = value;
        this.key = key;
    }

    public int getKey() {
        return key;
    }

    public void setKey(int key) {
        this.key = key;
    }

    //升序
    @Override
    public int compareTo(Bianhao o) {
        return this.getValue().compareTo(o.getValue());
    }
    public Integer getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }
}

3.2暴力破解

public class Solution1 {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int max = 0;
        for (int i = 0; i < len - 1; i++) {
            int a = prices[i];
            for (int j = i+1; j < len; j++) {
                if (prices[j] - a > max) {
                    max = prices[j] - a;
                }
            }
        }
        return max;
    }
}

简单暴力，缺点在于耗时，但也强于上一种做法

3.3 One pass

public class Solution2 {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int max = 0;
        for(int i = 0;i<prices.length;i++){
            if(prices[i]<minPrice){
                minPrice = prices[i];
            }
            if(prices[i]-minPrice>max){
                max = prices[i] - minPrice;
            }
        }
        return max;
    }
}

该做法的想法是，只用关注最小值和最大利润，每次更新最小值，同时算出当前的利润，若该利润大于之前的最大利润，则更新最大利润，如此一轮循环下来便求得了最大利润。

4.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 []numbers,int target){
        HashMap<Integer,Integer> map = new HashMap();
        for(int i = 0;i<numbers.length;i++){
            int b  = target - numbers[i];
            if(map.containsKey(b)){
                return new int[]{map.get(b)+1,i+1};
            }
            //处理完之后再将数据放进去，可以保证处理的时候不包含当前这个数据。
            map.put(numbers[i],i);
        }
        return null;
    }

注意这个的一个问题：处理的时候不能包含当前的数据，所以在判断之后再将数据放入，这里是不会出现问题的，因为如果应该存在的数据还未放入而导致第一次没找到，但他后续找到该数据的时候也会成功找到与之匹配的前一个数据。
例如：[1,2,3,4]，target = 7时。当放3号数据时，会发现没有匹配项，但接着到4时，就会找到相应的数据。

3.ThreeSum

public class Solution1 {
    public List<List<Integer>> threeSum(int[] nums) {
        //判断是否合法
        if (nums == null || nums.length < 3)
            return new ArrayList<>();
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            //不能和前一个相同，例如前一个为0,那么让twosum也去找0，如果这次还是让twosum去找0，则会出现重复。
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            twoSum(nums, i + 1, nums.length - 1, -nums[i], result);
        }
        return result;
    }

    public void twoSum(int nums[], int startIndex, int endIndex, int target, List<List<Integer>> result) {
        //因为已经排好序了，直接按小数+大数是否等于0来判断即可
        while (startIndex < endIndex) {
            if (nums[startIndex] + nums[endIndex] == target) {
                int num1 = nums[startIndex];
                int num2 = nums[endIndex];
                result.add(Arrays.asList(nums[startIndex], nums[endIndex],-target));
                //前后都应当改变，否则不平衡，就例如要找0，本来是-1 + 1 =0,若仅增大-1，那是找不到答案的，1也得减少。
                while (startIndex < endIndex && nums[startIndex] == num1) startIndex++;
                while (startIndex < endIndex && nums[endIndex] == num2) endIndex--;
            } else if (nums[startIndex] + nums[endIndex] < target) {
                startIndex++;
            } else {
                endIndex--;
            }
        }
    }
}

与2sum的区别在于，2sum要求给出index，而3sum只要求给出这个数就可以了。