【算法训练-数组 二】【元素组合】两数之和、三数之和

输入：
[3,2,4],6
返回值：
[2,3]
说明：
因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以返回[2,3]

输入：
[20,70,110,150],90
返回值：
[1,2]
说明：
20+70=90

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型一维数组
     * @param target int整型
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        // 1 用哈希表记录出现过的数字，key为数字，value为下标
        Map<Integer, Integer> map = new HashMap<>();
        int[] result = new int[2];
        for (int i = 0; i < numbers.length; i++) {
            // 得出需要的差值是多少
            int needVal = target - numbers[i];
            if (map.containsKey(needVal)) {
                // 如果map存储了差值则记录两数
                result[0] = map.get(needVal);
                result[1] = i + 1;
            } else {
                // 如果map未存储差值则将当前值存储
                map.put(numbers[i], i + 1);
            }
        }
        return result;
    }
}

输入：
[0]
返回值：
[]

输入：
[-2,0,1,1,2]
返回值：
[[-2,0,2],[-2,1,1]]

输入：
[-10,0,10,20,-10,-40]
返回值：
[[-10,-10,20],[-10,0,10]]

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        // 1 定义返回结果
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        // 排除不满足条件的num
        if (num == null || num.length < 3) {
            return result;
        }
        // 2 要求非降序排列，且为了应用左右指针及去重考虑，先对整个数组升序排列
        Arrays.sort(num);
        // 3 遍历数组，以其中一个数为基准，双指针寻找另外两个数
        for (int i = 0; i < num.length - 2; i++) {
            // 减少无效遍历，去掉无效情况,如果第一个数都大于0，那总和一定大于0
            if (num[i] > 0) {
                break;
            }
            // 排除基准数的重复值
            if (i > 0 && num[i] == num[i - 1]) {
                continue;
            }
            int left = i + 1, right = num.length - 1;
            int target = -num[i];
            while (left < right) {
                if (num[left] + num[right] == target) {
                    // 存放满足条件的三元组并移动指针
                    result.add(new ArrayList<>(Arrays.asList(num[i], num[left], num[right])));
                    // 基准数固定，指针移动，左指针向右，右指针必须向左【左+右】为固定值，如果左值不变，右值也不变就重复了，如果左值变，右值就不可能和原来一致，所以必须向左寻求新值。
                    left++;
                    right--;
                    // 由于数组已经排序，所以可能出现重复三元组的数据就在相邻位置，所以需要越过相邻位置的重复三元组
                    while (left < right && num[left] == num[left - 1]) {
                        left++;
                    }
                    while (left < right && num[right] == num[right + 1]) {
                        right--;
                    }
                } else if (num[left] + num[right] > target) {
                    // 大于目标值，右指针向左减小总值
                    right--;
                } else {
                    // 小于目标值，左指针向右扩大总值
                    left++;
                }
            }
        }
        return result;
    }
}