以前的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.
Read full article from Google – K Index
No comments:
Post a Comment