两数之和（2sum）

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解决方法

• 方法一：哈希表
  通过哈希表对给定的数组进行一次性遍历，将数组元素和元素下表存在哈希表中，因为最终要得出数组中元素的位置，所以将元素值存储在key中，将元素下表存储在value中。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int res[]={-1,-1};
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(target-nums[i])){
                res[0]=map.get(target-nums[i]);
                res[1]=i;
            }
            map.put(nums[i],i);
        }
            return res;
    }
}

哈希表
哈希表是由一组键值对组成（key-value），相比数组，线性链表，二叉树等数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)。
具体参考 https://www.cnblogs.com/chengxiao/p/6059914.html#t1
几种常用的方法

1. containsKey()
   containsKey() 的作用是判断HashMap是否包含key。

public boolean containsKey(Object key) {
    return getEntry(key) != null;
}
//containsKey() 首先通过getEntry(key)获取key对应的Entry，然后判断该Entry是否为null。

2. containsValue()
   containsValue() 的作用是判断HashMap是否包含“值为value”的元素。

public boolean containsValue(Object value) {
    // 若“value为null”，则调用containsNullValue()查找
    if (value == null)
        return containsNullValue();

    // 若“value不为null”，则查找HashMap中是否有值为value的节点。
    Entry[] tab = table;
    for (int i = 0; i < tab.length ; i++)
        for (Entry e = tab[i] ; e != null ; e = e.next)
            if (value.equals(e.value))
                return true;
    return false;
}

3. get()
   get() 的作用是获取key对应的value。

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    // 获取key的hash值
    int hash = hash(key.hashCode());
    // 在“该hash值对应的链表”上查找“键值等于key”的元素
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

4. put()
   put() 的作用是对外提供接口，让HashMap对象可以通过put()将“key-value”添加到HashMap中。

public V put(K key, V value) {
    // 若“key为null”，则将该键值对添加到table[0]中。
    if (key == null)
        return putForNullKey(value);
    // 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        // 若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    // 若“该key”对应的键值对不存在，则将“key-value”添加到table中
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

• 方法二：遍历法
  定义一个类似于指针的int，相当于确定了一个数，然后遍历一遍数组，寻找值为target-nums[i]的元素，得出他的位置i，如果存在这样一个数，得出最后答案，如果没有，自加。

 class Solution {
    public int[] twoSum(int[] nums, int target) {
        int res[]={-1,-1};
        for(int i=0;i<nums.length-1;i++){
            int left=i+1,num=target-nums[i];
            while(left<nums.length){
                if(nums[left]==num){
                res[0]=i;
                res[1]=left;
            }
                left++;
            }
        }
        return res;
    }
}

三数之和（3sum）

题目描述

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

• 方法
  整体的思想是将3sum化简称为2sum，定义左右两个指针，先对整个数组进行排序。遍历数组，先确定一个数，然后判断，是否存在nums[left]+nums[right]==0-nums[i],存在就将它们存到List里面。
  在3sum中还有一个值得注意的地方就是，去重，如果重复，则left++，right--。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        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,right=nums.length-1,num=0-nums[i];
            while(left<right){
                if(nums[left]+nums[right]==num){
                    res.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while(left<right&&nums[left]==nums[left+1]) left++;
                    while(left<right&&nums[right]==nums[right-1]) right--;
                    left++;
                    right--;
                }else if(nums[left]+nums[right]<num) left++;
                else right--;
            }
        }
        return res;
    }
}