Container With Most Water leetcode

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.

brute force方法是对每一对都求面积, 然后比较面积 要遍历两次  时间复杂度O(n^2)

另外一种方法是two points的方法, 从两头开始计算面积, 因为蓄水面积是由短板决定的, 每次比较左右point 哪个是短板就移动哪一个, 这样只扫面一次数组 时间O(n)

public class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int left = 0;
        int right = height.length - 1;
        int area = 0;
        while (left < right) {
            area = Math.max(area, Math.min(height[left], height[right]) * (right - left));
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return area;
    }
}

Sort Colors leetcode

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

第一种简便的算法, 只扫描一次 所以为O(n)

就是有两个指针 一个代表0 一个代表1 扫描的i代表2 

如果出现0 所有指针赋值并且往前走 遇到1 1指针和i往前走 遇到2 i往前走

public class Solution {
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int index0 = 0;
        int index1 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                nums[i] = 2;
                nums[index1++] = 1;
                nums[index0++] = 0;
            } else if (nums[i] == 1) {
                nums[i] = 2;
                nums[index1++] = 1;
            }
        }
    }
}

方法2 :
我们先用两个指针，一个指向已经排好序的0的序列的后一个点，一个指向已经排好序的2的序列的前一个点。这样在一开始，两个指针是指向头和尾的，因为我们还没有开始排序。然后我们遍历数组，当遇到0时，将其和0序列后面一个数交换，然后将0序列的指针向后移。当遇到2时，将其和2序列前面一个数交换，然后将2序列的指针向前移。遇到1时，不做处理。这样，当我们遍历到2序列开头时，实际上我们已经排好序了，因为所有0都被交换到了前面，所有2都被交换到了后面。时间复杂度O(n)

public class Solution {
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }    
        int left = 0, right = nums.length - 1, i = 0;
        while (i <= right) {
            if (nums[i] == 0) {
                swap(nums, left, i);
                left++;
                i++;//指针从左边过来 所以左边是有序的
            } else if (nums[i] == 2) {
                swap(nums, right, i);
                right--;
            } else {
                i++;
            }
        }
    }
    private void swap(int[] nums, int i1, int i2){
        int tmp = nums[i1];
        nums[i1] = nums[i2];
        nums[i2] = tmp;
    }
}

另外一种计数排序.首先便利一次统计每个元素的个数 然后根据颜色出现的次数分别对原数组进行修改.这个方法遍历数组两次.时间也是O(n)

public class Solution {
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int[] colors = new int[3];
        for (int i = 0; i < nums.length; i++) {
            colors[nums[i]]++;
        }
        int index = 0;
        for (int i = 0; i < colors.length; i++) {
            for (int j = 0; j < colors[i]; j++) {
                nums[index] = i;
                index++;
            }
        }
    }
}

4Sum leetcode

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

与3sum相同 但是多了一层循环 时间复杂O(n^3)

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 3; i++) {
            if (i > 0 && nums[i] == nums[i-1]) {//如果i重复取 结果相同
                continue;
            }
            for (int j = i + 1; j < nums.length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int left = j + 1;
                int right = nums.length - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        List<Integer> tem = new ArrayList<Integer>();
                        tem.add(nums[i]);
                        tem.add(nums[j]);
                        tem.add(nums[left]);
                        tem.add(nums[right]);
                        res.add(tem);
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right + 1]) {
                            right --;
                        }
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return res;
    }
}

3Sum Closest leetcode

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

    For example, given array S = {-1 2 1 -4}, and target = 1.

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

3sum的变体, 维护一个close记录abs(sum- target)的最小值
如果有sum = target 就返回sum 否则就返回close 排序时间O(nlogn) + 查找O(n^2)=
时间复杂度 O(n^2)

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if (nums.length < 3 || nums == null) {
            return Integer.MAX_VALUE;
        }
        int close = Integer.MAX_VALUE - Math.abs(target);//防止溢出
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum =nums[i] + nums[left] + nums[right];
                if (sum == target) {
                    return sum;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
                if (Math.abs(close - target) > Math.abs(sum - target)){
                    close = sum;
                }
            }
        }
        return close;
    }
} 

3Sum leetcode

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

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

把数组从0到length - 3 进行遍历 , nums[i]为第一个数 从i + 1 到len -1 用2sum的双指针方法查找 找到一个解之后挪动指针继续查找

要注意数组中的重复问题

遍历的复杂度是O(n) 双指针查找的复杂度是O(n) 所以时间复杂度O(n^2)

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums.length < 3 || nums == null) {
            return res;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {//防止出现重复
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    List<Integer> tem = new ArrayList<Integer>();
                    tem.add(nums[i]);
                    tem.add(nums[left]);
                    tem.add(nums[right]);
                    res.add(tem);
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;//防止数组出现重复
                    }
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }
        }
        return res;
    }
}