两数之和（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
几种常用的方法
- containsKey()
containsKey() 的作用是判断HashMap是否包含key。
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
//containsKey() 首先通过getEntry(key)获取key对应的Entry，然后判断该Entry是否为null。
- 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;
}
- 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;
}
- 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;
}
}
