算法原型

/**
 1. 求数组中等于给定值的最长子数组
 */
public class LongestSubArrayEqualsAim {

    public static int solve(int[] arr, int target) {
        if (arr == null || arr.length == 0)
            return 0;

        //key:sum value:pos
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int res = 0;
        int sum = 0;

        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (map.containsKey(sum - target)) {
                res = Math.max(i - map.get(sum - target), res);
            }

            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {7, 1, 2, 3, 1, 4, 2, 1, -1, -2, 1, 2, -7, 7, 6, 3};
        int[] arr1 = {7, 7, 7, 7, 7, 7, 7, 7, 1, 2, 3, 1};
        System.out.println(solve(arr, 7));
        System.out.println(solve(arr1, 7));
    }
}

算法扩展

一个数组中既有奇数又有偶数，求奇数和偶数个数相等的最长的子数组

思路：将奇数记为-1，偶数记为1，题目转换为求数组中等于0的最长子数组

 public static int solve1(int[] arr) {
        if (arr == null || arr.length == 0)
            return 0;

        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & 1) == 1) {
                arr[i] = -1;
            } else {
                arr[i] = 1;
            }
        }

        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int sum = 0;
        int res = 0;

        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (map.containsKey(sum)) {
                res = Math.max(i - map.get(sum), res);
            }
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
        }
        return res;
    }