数组、字符串与哈希结构数组、字符串与哈希结构

public final class RangeSum {
    private final long[] prefix;

    public RangeSum(int[] nums) {
        this.prefix = new long[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }

    public long query(int left, int right) {
        if (left < 0 || right >= prefix.length - 1 || left > right) {
            throw new IllegalArgumentException("invalid range");
        }
        // [left, right] = 前 right+1 个 - 前 left 个
        return prefix[right + 1] - prefix[left];
    }
}

// 预处理 O(n)，单次查询 O(1)，空间 O(n)

import java.util.HashMap;
import java.util.Map;

public final class TwoSum {
    private TwoSum() {
    }

    public static int[] solve(int[] nums, int target) {
        Map<Integer, Integer> indexByValue = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            Integer matchedIndex = indexByValue.get(complement);
            if (matchedIndex != null) {
                return new int[]{matchedIndex, i};
            }

            // 先查询再写入，避免同一元素被使用两次
            indexByValue.put(nums[i], i);
        }
        return new int[0];
    }
}