Google – K Index

Google – K Index
以前的K sum 问题是给一个数组和一个target，找出数组里是否有k个数的和为target。这道K index问题稍微有点不一样，要求是找出数组里是否有k个数，使得k – 1个数的和为最后一个数: nums[i] + … + nums[j] = nums[k]
[Solution]
蛮难的一道题。不知道做得对不对。。
还是DP, lookup[k][j]表示是否有k – 1个数相加等于nums[j]。
lookup[k][j] = lookup[k – 1][t] && (nums[j] – nums[t]) in nums[] && (nums[j] – nums[t])的index和那k – 1个数不同, where t ∈ [0, j)
Base case: lookup[2][j] = true
time: O(k * n * n)
space: O(k * n * k), 因为对于每个lookup[k][j]都要存下k个数的index以防止后面使用重复的index.

  public boolean kIndex(int[] nums, int k) {

    if (nums == null || nums.lenght == 0 || k == 0) {

      return false;

    }

 

    int n = nums.length;

    Map<Integer, List<Integer>> map = new HashMap<>();

    Map<Integer, Map<Integer, Set<Integer>>> indexMap = new HashMap<>();

    for (int i = 0; i < n; i++) {

      map.putIfAbsent(nums[i], new ArrayList<>());

      map.get(nums[i]).add(i);

    }

 

    int[][] lookup = new int[k + 1][n];

    for (int j = 0; j < n; j++) {

      lookup[2][j] = true;

      indexMap.putIfAbsent(2, new HashMap<>());

      indexMap.get(2).putIfAbsent(nums[j], new HashSet<>());

      indexMap.get(2).get(nums[j]).add(j);

    }

 

    for (int i = 3; i <= k; i++) {

      for (int j = 0; j < n; j++) {

        for (int t = 0; t < j; t++) {

          if (lookup[i - 1][t] && map.containsKey(nums[j] - nums[t])) {

            Set<Integer> set = indexMap.get(i - 1).get(nums[t]);

            int newIndex = -1;

            for (int x : map.get(nums[j] - nums[t])) {

              if (!set.contains(x)) {

                newIndex = x;

                break;

              }

            }

            if (newIndex != -1) {

              Set<Integer> newSet = new HashSet<>(set);

              newSet.add(newIndex);

              indexMap.putIfAbsent(i, new HashMap<>());

              indexMap.get(i).put(nums[j], newSet);

              lookup[i][j] = true;

            }

          }

        }

      }

    }

    return lookup[k][n - 1];

  }

Read full article from Google – K Index