哈希

BM50 两数之和

public class Solution {
    public int[] twoSum (int[] numbers, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < numbers.length; i++) {
            map.put(target - numbers[i], i);
        }
        int[] ans = new int[2];
        for(int i = 0; i < numbers.length; i++){
            if(map.containsKey(numbers[i])){
                int index = map.get(numbers[i]);
                if(i == index) continue;
                
                ans[0] = (i < index ? i : index) + 1;
                ans[1] = (i > index ? i : index) + 1;
            }
        }
        return ans;
    }
}

BM51 数组中出现次数超过一半的数组

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        // 摩尔投票法
        int ans = array[0], count = 1;
        for (int i = 1; i < array.length; i++) {
            if (array[i] == ans){
                count++;
                continue;
            }
            count--;
            if(count == 0) {
                ans = array[i];
                count++;
            }
        }
        return ans;
    }
}

BM 52 数组中只出现一次的两个数字

public class Solution {
    public int[] FindNumsAppearOnce (int[] array) {
        int ans[] = new int[2];
        int number = 0;
        for(int i = 0; i < array.length; i++){
            number ^= array[i];
        }
        // 找出a和b中不同的位
        int mask = 1;
        while((number & mask) == 0) mask <<= 1;
        // 按mask位为0和1区分
        //,首先这两个数一定不同,故异或结果一定不为0,那么a异或b的结果中一定有一位为1,
        //假设是第x位,那么就说明了a和b的二进制的第x位是不同,根据这一特点,
        //我们可以将数组分为两个集合,即第x位为1的数和第x位为0的数,两部分的异或和即为a和b的值
        for(int i = 0; i < array.length; i++){
            if((array[i] & mask) == 0) ans[0] ^= array[i];
            else ans[1] ^= array[i];
        }
        // 小在前，大在后
        if(ans[0] > ans[1]){
            ans[0] = ans[0] ^ ans[1];
            ans[1] = ans[0] ^ ans[1];
            ans[0] = ans[0] ^ ans[1];
        }
        return ans;
    }
}

BM53 缺失的第一个正整数

public class Solution {
    public int minNumberDisappeared (int[] nums) {
        // 通过交换位置，在遍历确定
        int len = nums.length;
        loop : for(int i = 0; i < len; i++){
            // 若当前位置值与i + 1不相等
            while(nums[i] != i + 1){
                //值大于len，或者<=0，则跳过，进入下一个位置
                if(nums[i] <= 0 || nums[i] > len) continue loop;
                swap(nums, i, nums[i] - 1);
            }
        }
        for(int i = 0; i < len; i++)
            if(nums[i] != i + 1) return i + 1;
        return len + 1;
    }
    
    public void swap(int[] nums, int index1, int index2){
        nums[index1] = nums[index1] ^ nums[index2];
        nums[index2] = nums[index1] ^ nums[index2];
        nums[index1] = nums[index1] ^ nums[index2];
    }
}

BM54 三数之和（注意）

import java.util.*;
public class Solution {
    // 两数之和
    public ArrayList<ArrayList<Integer>> twoSum (int[] nums, int start, int target) {
        // 先对数组进行排序
        //Arrays.sort(nums);
        // 定义左右指针
        int left = start, right = nums.length - 1;
        // 链表，用于存出结果
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        while(left < right){
            int sum = nums[left] + nums[right];
            // 记录左右指针位置的值
            int lowVal = nums[left], highVal = nums[right];
            // 用以判断
            if(sum < target){//left++
                while(left < right && lowVal == nums[left]) left++;
            } else if(sum > target){//right--
                while(left < right && highVal == nums[right]) right--;
            }else{//sum = target,添加结果
                ArrayList<Integer> arr = new ArrayList<Integer>();
                arr.addAll(Arrays.asList(lowVal, highVal));
                res.add(arr);
                // 跳过重复答案
                while(left < right && lowVal == nums[left]) left++;
                while(left < right && highVal == nums[right]) right--;
            }
        }
        return res;
    }

    // 计算三数之和为target的所有三元组
    public ArrayList<ArrayList<Integer>> threeSum(int[] nums, int target) {
        Arrays.sort(nums);
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < nums.length; i++) {
            ArrayList<ArrayList<Integer>> twoSum = twoSum(nums, i + 1, target - nums[i]);
            for (ArrayList<Integer> list : twoSum) {
                list.add(nums[i]);
                Collections.sort(list);// 进行排序
                res.add(list);
            }
            while(i < nums.length - 1 && nums[i] == nums[i + 1]) i++;
        }
        return res;
    }

    public ArrayList<ArrayList<Integer>> threeSum(int[] nums) {
        return threeSum(nums, 0);
    }
}