Facebook 电面

1. vector<int> rangeSum(vector<int>& nums, int target) {
   
2.         vector<int> sum(nums.size() + 1, 0);
   
3.         vector<int> res;
   
4.         unordered_map<int, int> map;
   
5.         sum[0] = 0;
   
6.         //得到sum数组， sum[i] 为 num[0]+...+num[i-1]的和， sum[0]为0
   
7.         //问题转化为求满足 sum[j] - sum[i] == target 的解 (j>i) 即 nums在[i,j-1]的和
   
8.         for(int i = 0; i < nums.size(); i++) {
   
9.                 sum[i + 1] = sum[i] + nums[i];
   
10.         }
    
11.         //使用hashmap, key为sum[i] + target, value为i. 当找到sum[j] == sum[i] + target时返回此时的index
    
12.         for(int i = 0; i < sum.size(); i++) {
    
13.                 if(map.find(sum[i]) == map.end()) {
    
14.                         map[sum[i] + target] = i;
    
15.                 }else {
    
16.                         res.push_back(map[sum[i]]);
    
17.                         res.push_back(i-1);
    
18.                         return res;
    
19.                 }
    
20.         }
    
21.         return res;
    
22. }

复制代码

第二题subarray sum吧，lintcode有类似的题

wszk1992 发表于 2016-7-19 22:18

这个好像是对的..但是你这里的sum[i] 是

sum[i] 为 num[0]+...+num[i-1]的和


而你上一个帖子说的是

sum[i] 为 num[0]+...+num[i]的和


...

试做一下第二题，应该是lintcode上subarray sum的变形：
public ArrayList<Integer> subarraySum(int[] nums, int target) {
    ArrayList<Integer> res = new ArrayList<>();
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(0, -1);
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (map.containsKey(sum - target)) {
            res.add(map.get(sum - target) + 1);
            res.add(i);
            return res;
        } else {
            map.put(sum, i);
        }
    }    return res;
}

上面答案是求出符合答案的任意区间即返回的情况。如果要求写出所有符合的区间，那可能要建一个HashMap<Integer, ArrayList<Integer>>，用arraylist来储存所有sum相同的index，每当遇到map.containsKey(sum)的情况就往arraylist里加当前index，而当map.containsKey(sum - target)时就把那个arraylist里的index都for一遍来输出区间结果，如[index1 + 1, i]，[index2 + 1, i]等等。

第二题只要返回true/false就行，不需要都找出来

mymulife 发表于 2016-7-20 00:57
第二题只要返回true/false就行，不需要都找出来

那就好，index都不用记了，一个hashset可以

Badger96 发表于 2016-7-20 00:11
试做一下第二题，应该是lintcode上subarray sum的变形：
public ArrayList subarraySum(int[] nums, int t ...

这个0,-1的corn case 解决的不错!

readman 发表于 2016-7-20 02:17
这个0,-1的corn case 解决的不错!

谢谢这个专门用来解决第一项即为结果的情况

Badger96 发表于 2016-7-20 01:26
那就好，index都不用记了，一个hashset可以

还是要记住index吧。。。比如。arr = [1,2,3] . 所以 sum[] = [1,3,6]. 如果 target = -5 （不能实现）。当int i=0的时候，sum[0]等于1. target-sum[0] 等于6. 在hashset里，就错了。所以还是要HashMap. 感觉。

997562971@qq.co 发表于 2016-7-31 07:59
还是要记住index吧。。。比如。arr = [1,2,3] . 所以 sum[] = [1,3,6]. 如果 target = -5 （不能实现）。 ...

i = 0时还没把6添加进hashset啊，i = 3时才会把6加进去。你如果一开始先把后面的sum加进去当然会错了