BM50 两数之和
哈希表
import java.util.*;
public class Solution {
public int[] twoSum (int[] numbers, int target) {
int[] res = new int[0];
//创建哈希表,两元组分别表示值、下标
HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
//在哈希表中查找target-numbers[i]
for(int i = 0; i < numbers.length; i++){
int temp = target - numbers[i];
//若是没找到，将此信息计入哈希表
if(!hash.containsKey(temp))
hash.put(numbers[i], i);
//否则返回两个下标+1
else
return new int[] {hash.get(temp) + 1, i + 1};
}
return res;
}
}
BM54 三数之和
哈希表和双指针
step 1：排除边界特殊情况。
step 2：既然三元组内部要求非降序排列，那我们先得把这个无序的数组搞有序了，使用sort函数优先对其排序。
step 3：得到有序数组后，遍历该数组，对于每个遍历到的元素假设它是三元组中最小的一个，那么另外两个一定在后面。
step 4：需要三个数相加为0，则另外两个数相加应该为上述第一个数的相反数，我们可以利用双指针在剩余的子数组中找有没有这样的数对。双指针指向剩余子数组的首尾，如果二者相加为目标值，那么可以记录，而且二者中间的数字相加可能还会有。
step 5：如果二者相加大于目标值，说明右指针太大了，那就将其左移缩小，相反如果二者相加小于目标值，说明左指针太小了，将其右移扩大，直到两指针相遇，剩余子数组找完了。
注：对于三个数字都要判断是否相邻有重复的情况，要去重
时间复杂度：O(n^2)，排序的复杂度为O(nlog_2n)，查找三元组的复杂度为O(n^2)
空间复杂度：O(1)，res属于必要空间，不属于额外空间，无其他辅助空间
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>();
int n = num.length;
//不够三元组
if(n < 3)
return res;
//排序
Arrays.sort(num);
for(int i = 0; i < n - 2; i++){
if(i != 0 && num[i] == num[i - 1])
continue;
//后续的收尾双指针
int left = i + 1;
int right = n - 1;
//设置当前数的负值为目标
int target = -num[i];
while(left < right){
//双指针指向的二值相加为目标，则可以与num[i]组成0
if(num[left] + num[right] == target){
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.add(num[i]);
temp.add(num[left]);
temp.add(num[right]);
res.add(temp);
while(left + 1 < right && num[left] == num[left + 1])
//去重
left++;
while(right - 1 > left && num[right] == num[right - 1])
//去重
right--;
//双指针向中间收缩
left++;
right--;
}
//双指针指向的二值相加大于目标，右指针向左
else if(num[left] + num[right] > target)
right--;
//双指针指向的二值相加小于目标，左指针向右
else
left++;
}
}
return res;
}
}
BM51 数组中出现次数超过一半的数字
遍历一遍
import java.util.*;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int targrt =array[0];
int n= 1;
for(int i=1;i<array.length;i++){
if(array[i]==targrt){
n++;
}else{
n--;
if(n==0){
targrt = array[i];
n=1;
}
}
}
return targrt;
}
}
空间复杂度 O(1)，时间复杂度 O(n)
BM52 数组中只出现一次的两个数字
一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
空间复杂度 O(1)，时间复杂度 O(n);
异或算法
step 1：遍历整个数组，将每个元素逐个异或运算，得到a⊕b a \oplus b。
step 2：我们可以考虑位运算的性质，找到二进制中第一个不相同的位，将所有数组划分成两组。
step 3：遍历数组对分开的数组单独作异或连算。
step 4：最后整理次序输出。
import java.util.*;
public class Solution {
public int[] FindNumsAppearOnce (int[] array) {
int res1 = 0;
int res2 = 0;
int temp = 0;
//遍历数组得到a^b
for(int i = 0; i < array.length; i++)
temp ^= array[i];
int k = 1;
//找到两个数不相同的第一位
while((k & temp) == 0)
k <<= 1;
for(int i = 0; i < array.length; i++){
//遍历数组，对每个数分类
if((k & array[i]) == 0)
res1 ^= array[i];
else
res2 ^= array[i];
}
//整理次序
if(res1 < res2)
return new int[] {res1, res2};
else
return new int[] {res2, res1};
}
}
BM53 缺失的第一个正整数
给定一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数
空间复杂度 O(1)，时间复杂度 O(n);
原地哈希
step 1：我们可以先遍历数组将所有的负数都修改成n+1。
step 2：然后再遍历数组，每当遇到一个元素绝对值不超过n时，则表示这个元素是1～n中出现的元素，我们可以将这个数值对应的下标里的元素改成负数，相当于每个出现过的正整数，我们把与它值相等的下标都指向一个负数，这就是类似哈希表的实现原理的操作。
step 3：最后遍历数组的时候碰到的第一个非负数，它的下标就是没有出现的第一个正整数，因为它在之前的过程中没有被修改，说明它这个下标对应的正整数没有出现过。
import java.util.*;
public class Solution {
public int minNumberDisappeared (int[] nums) {
int n = nums.length;
//遍历数组
for(int i = 0; i < n; i++)
//负数全部记为n+1
if(nums[i] <= 0)
nums[i] = n + 1;
for(int i = 0; i < n; i++)
//对于1-n中的数字
if(Math.abs(nums[i]) <= n)
//这个数字的下标标记为负数
nums[Math.abs(nums[i]) - 1] = -1 * Math.abs(nums[Math.abs(nums[i]) - 1]);
for(int i = 0; i < n; i++)
//找到第一个元素不为负数的下标
if(nums[i] > 0)
return i + 1;
return n + 1;
}
}