字节跳动面试算法题：返回一个数组（包含负数）连续区间和等于k的下标1.题目描述2.解题思路3.代码实现相似题目代码实现

107 阅读 0 评论 71 点赞

我是靠谱客的博主冷静招牌，最近开发中收集的这篇文章主要介绍字节跳动面试算法题：返回一个数组（包含负数）连续区间和等于k的下标1.题目描述2.解题思路3.代码实现相似题目代码实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.题目描述

给定一个数组，判断数组内是否存在一个连续区间，使其和恰好等于给定整数k。

输入：
输入包含多组测试用例，每组测试用例由一个整数n(1<=n<=10000)开头，代表数组的大小。
接下去一行为n个整数，描述这个数组，整数绝对值不大于100。
最后一行为一个整数k(大小在int范围内)。

输出：
对于每组测试用例，若存在这个连续区间，输出其开始和结束的位置，s，e(s <= e)。
若存在多个符合条件的输出，则输出s较小的那个，若仍然存在多个，输出e较小的那个。
若不存在，直接输出"No"。

样例输入：
5
-1 2 3 -4 9
5
3
-1 2 -3
7
2
-1 1
0
样例输出：
2 3
No
1 2

2.解题思路

记录前缀和 sum[i] = nums[0] + nums[1] + .... + nums[i-1]，sum[0] =0

如果 sum[j]-sum[i]==k，说明 [ nums[i]，nums[j-1] ]，j-1>=i，这之间的数符合条件，sum[end]=sum[start]+k

利用一个hash表的key和value存储所有的sum[i]与[i]，因为有不同的i使得sum[i]相同，所以，value实际是个list

从1到n遍历start，固定start，s=sum[end]=sum[start]+k，看hash表中是否有s这个key，如果有的话，找到s的第一个大于等于start的下标，即为end

3.代码实现

实现一：（麻烦，不推荐）

def subArrayTarget(n, nums, k):
    sum = [0] * (n + 1)
    hash = {}
    for i in range(1, n + 1):
        sum[i] = sum[i - 1] + nums[i - 1]
        if sum[i] not in hash:
            hash[sum[i]] = [i]
        else:
            hash[sum[i]].append(i)
    for start in range(0, n + 1):
        s = sum[start] + k
        if s in hash:
            ends = hash[s]
            for e in ends:
                if e >= start+1:
                    print(start+1, e)
                    return
    print("No")


subArrayTarget(5, [-1, 2, 3, -4, 9], 5)
subArrayTarget(3, [-1, 2, 3], 7)
subArrayTarget(2, [-1, 1], 0)
subArrayTarget(9,[1,1,2,2,1,1,3,4,5],4)

"""
输出：
2 3
No
1 2
1 3
"""

实现二：输出的是所有可能的组合

def subArrayTarget(n, nums, k):
    print("-----")
    hash = {}
    # 注意这里要事先加入
    # 此类题型，如果是涉及角标输出的，设置的都是-1，但是如果是个数的话，这里是1，参考
    # leetcode560 和为 k 的连续的子数组的个数
    hash[0] = -1
    sum = 0
    for i in range(n):
        sum = sum + nums[i]
        if sum - k in hash:
            j = hash[sum-k]
            # 输出所有可能的组合
            print(j+1,i)
        if sum not in hash:
            hash[sum] = i

subArrayTarget(5, [-1, 2, 3, -4, 9], 5)
subArrayTarget(3, [-1, 2, 3], 7)
subArrayTarget(2, [-1, 1], 0)
subArrayTarget(9,[1,1,2,2,1,1,3,4,5],4)
subArrayTarget(3,[1,1,1],2)


"""
-----
1 2
3 4
-----
-----
0 1
-----
0 2
2 3
3 5
5 6
7 7
-----
0 1
1 2

"""

相似题目

给定一个无序数组arr，其中元素可正，可负，可0，给定一个整数k。求arr所有的子数组中累加和为k的最长子数组长度。

来源：程序员代码面试指南

代码实现

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

public class _01_Array_maxLength {
    public int maxLength(int[] arr, int k) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        # 注意 加入-1
        map.put(0, -1);
        int len = 0;
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (map.containsKey(sum - k)) {
                # 根据题目要求变换代码
                len = Math.max(i - map.get(sum - k), len);
            }
            # 注意这里，是sum是否存在，不是sum-k是否存在哦
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
        }
        return len;
    }
}