算法练习第三天

1. 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

方法一：暴力枚举
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}
方法二：哈希表
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}
说明：如果数组有序，则可以通过两个指针移动实现，如果无序，则可以通过排序、或者hashMap实现

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        // 第一步：排序
        Arrays.sort(nums);
        // 第二步：枚举a
        for(int a = 0 ; a < n ; a++){
            // 防止重复
            if(a > 0 && nums[a] == nums[a-1]){
                continue;
            }
            // 第三步：通过指针，c指向最右边最大的那个值
            int c = n-1;
            // b和c两个指针，寻找target值
            int target = 0 - nums[a];
            // 第四步：枚举b
            for(int b = a+1; b < n; b++){
                // 防止重复
                if(b > a+1 && nums[b] == nums[b-1]){
                    continue;
                }
                // c指针一直向左移动
                while(b < c && nums[b] + nums[c] > target){
                    c--;
                }
                // 相遇，则这轮结束
                if(b == c){
                    break;
                }
                // 找到了
                if(nums[b] + nums[c] == target){
                    List<Integer> midRes = new ArrayList<>();
                    midRes.add(nums[a]);
                    midRes.add(nums[b]);
                    midRes.add(nums[c]);
                    res.add(midRes);
                }
            }
        }
        return res;
    }
}

121. 买卖股票的最佳时机

示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

class Solution {
    public int maxProfit(int[] prices) {
        int curMin = prices[0];
        int sum = 0;
        for(int i = 1 ; i < prices.length ; i++){
            sum = Math.max(sum , prices[i] - curMin);
            // 遍历过程中，记录当前最小值
            curMin = Math.min(curMin, prices[i]);
        }
        return sum;
    }
}

122. 买卖股票的最佳时机 II

示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

class Solution {
    public int maxProfit(int[] prices) {
        int sum = 0;
        for(int i = 0; i < prices.length -1 ; i++){
            if(prices[i] < prices[i+1]){
                sum +=  prices[i+1] - prices[i];
            }
        }
        return sum;
    }
}

53. 最大子序和

示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

class Solution {
    public int maxSubArray(int[] nums) {
        // 当前遍历的最大连续和
        int curSum = 0, totalSum = nums[0];
        for (int x : nums) {
            curSum = Math.max(curSum + x, x);
            totalSum = Math.max(totalSum, curSum);
        }
        return totalSum;
    }
}

152. 乘积最大子数组

示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

class Solution {
    public int maxProduct(int[] nums) {
        int maxF = nums[0], minF = nums[0], ans = nums[0];
        int length = nums.length;
        for (int i = 1; i < length; ++i) {
            int mx = maxF, mn = minF;
            maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));
            minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));
            ans = Math.max(maxF, ans);
        }
        return ans;
    }
}