LintCode 子数组之和题目分析代码

题目

给定一个整数数组,找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置

样例 给出 [-3, 1, 2, -3, 4],返回[0, 2]或者 [1, 3]

分析

这里用了一个技巧:将数组从第一位依次相加,记录每次的结果,如果map里面没有,就加入map里,如果有,就证明前面肯定有为0的子数组,才会出现一样的和。

代码

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number 
     *          and the index of the last number
     */
    public ArrayList<Integer> subarraySum(int[] nums) {
        // write your code here
        int len = nums.length;
       
        ArrayList<Integer> ans = new ArrayList<Integer>();
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
       
        map.put(0, -1);
       
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
           
            if (map.containsKey(sum)) {
                ans.add(map.get(sum) + 1);
                ans.add(i);
                return ans;
            }
            
            map.put(sum, i);
        }
       
        return ans;
    }
}

.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java帮帮-微信公众号-技术文章全总结

Java集合详解【面试+工作】

在说集合前我们不得不说一下数组 数组的作用: 存放一组相同的数据类型(基本或对象)的数据,从而实现对数据的管理 优势:可以快速的通过下标对数组元素进行访问,效率...

4356
来自专栏LinkedBear的个人空间

唠唠SE的集合-06——Set接口 原

注重独一无二的性质,该体系集合可以知道某物是否已经存在于集合中,不存储重复的元素。

773
来自专栏java一日一条

如何用Map对象创建Set对象

Java中的Map和Set有不少相似之处。本文将分享一个把Map类转化成Set类的小技巧。

711
来自专栏大数据钻研

Java集合类操作优化经验总结

本文首先针对 Java 集合接口进行了一些介绍,并对这些接口的实现类进行详细描述,包括 LinkedList、ArrayList、Vector、Stack、Ha...

38317
来自专栏令仔很忙

集合详解(三)----Map的两种遍历方式

Map是以键值对(key-value)的方式来存取值的,那么该怎么把Map中的值取出来的,有两种方式,往下看。先定义一个Map,向里面存放一些数据。

722
来自专栏互扯程序

Java常用集合源码级深度解析

Java集合工具包位于Java.util包下,包含了很多常用的数据结构,如数组、链表、栈、队列、集合、哈希表等。学习Java集合框架下大致可以分为如下五个部分:...

4956
来自专栏Java技术栈

Java码农必须掌握的循环删除List元素的正确方法!

首先看下下面的各种删除list元素的例子 public static void main(String[] args) { List<Stri...

35710
来自专栏Jack的Android之旅

疯狂Java笔记之常见java集合的实现细节

首先Set是一种集合元素无序,不可重复的集合。而Map则代表一种有多个key-value对组成的集合,Map集合类似于传统的关联数据。看起来他们没哟什么关联,实...

622
来自专栏Android机动车

数据结构学习笔记——线性表(上)

线性表元素的个数n(n≥0)定义为线性表的长度,当n=0时,称为空表。在非空表中的每个元素都有一个确定的位置,如a1是第一个元素,an是最后一个元素,ai是第i...

602
来自专栏JAVA高级架构

Java HashMap 遍历方式性能探讨

关于HashMap的实现这里就不展开了,具体可以参考 JDK7与JDK8中HashMap的实现 JDK8之前,可以使用keySet或者entrySet来遍历Ha...

41912

扫码关注云+社区