算法|hash

560. 和为 K 的子数组

class Solution {
    public int subarraySum(int[] nums, int k) {
        int preSum = 0;
        int result = 0;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            preSum += nums[i];
            if (hashMap.containsKey(preSum - k)) {
                result += hashMap.get(preSum - k);
            }
            hashMap.put(preSum, hashMap.getOrDefault(preSum, 0) + 1);
        }
        return result;
    }
}

974. 和可被 K 整除的子数组

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int result = 0;
        int preSum = 0;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            preSum += nums[i];
            int y = (preSum % k + k) % k;
            result += hashMap.getOrDefault(y, 0);
            hashMap.put(y, hashMap.getOrDefault(y, 0) + 1);
        }
        return result;
    }
}

12. 整数转罗马数字

class Solution {
    public String intToRoman(int num) {
         int[] nums = new int[] {1000,900,500,400,100,90,50,40,10,9,5,4,1};
         String[] strs = new String[] {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
         StringBuilder result = new StringBuilder();
         for (int i = 0; i < nums.length; i++) {
             while (num >= nums[i]) {
                 result.append(strs[i]);;
                 num = num - nums[i];
             }
         }
         return result.toString();
    }
}

41. 缺失的第一个正数

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        boolean[] flags = new boolean[n + 1];
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0 && nums[i] <= n) {
                flags[nums[i]] = true;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (!flags[i]) return i;
        }
        return n + 1;
    }
}

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // System.out.println(i + " " + nums[i] + " " + nums[nums[i] - 1]);
            while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
                //交换
                int temp = nums[i];
                nums[i] = nums[temp - 1];
                nums[temp - 1] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
}

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) nums[i] = n + 1;
        }
    
        for (int i = 0; i < n; i++) {
            int index = Math.abs(nums[i]);
            if (index <= n) {
                nums[index - 1] = -Math.abs(nums[index - 1]);
            }
        }
        for (int i = 0; i < n; i++) {
            System.out.println(nums[i]);
            if (nums[i] > 0) return i + 1;
        }
        return n + 1;
    }
}

268. 丢失的数字

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) return i;
        }
        return n;
    }
}

class Solution {
    public int missingNumber(int[] nums) {
        HashSet<Integer> hashSet = new HashSet<>();
        for (int num:nums) {
            hashSet.add(num);
        }
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (!hashSet.contains(i)) return i;
        }
        return n;
    }
}

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            //交换到相应位置
            while (nums[i] >= 0 && nums[i] < n && nums[i] != nums[nums[i]]) {
                int temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) return i;
        }
        return n;
    }
}

287. 寻找重复数

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) {
                slow = 0;
                while (slow != fast) {
                    slow = nums[slow];
                    fast = nums[fast];
                }
                return slow;
            }
        }
    }
}

442. 数组中重复的数据

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++){
            int v = Math.abs(nums[i]);
            if (nums[v - 1] > 0) {
                nums[v - 1] = -nums[v - 1];
            } else {
                result.add(v);
            }
        }
        return result;
    }
}

剑指 Offer 03. 数组中重复的数字

class Solution {
    public int findRepeatNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++){
            while (nums[i] != nums[nums[i]]){
                //没在相应的位置，交换
                int temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
            if (nums[i] != i) return nums[i];
        }
        return -1;
    }
}