找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 6102|回复: 5
收起左侧

[提问] CC150+Leetcode Continuous Subarray Sum II 请教问题

[复制链接]

50

主题

1

精华

303

积分

高级会员

Rank: 3Rank: 3

积分
303
发表于 6-11-2015 01:28 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
楼主不知道哪里出错了。。。在网上也没有搜到java的答案。。。

我的思路就是,像Continuous Subarray Sum一样按顺序走一遍,如果最后一个sum > 0, 则需要再从第一个扫一遍,一旦sum小于0,就停止

pass了11/18个test case,

代码如下
也请热心的同学帮忙做code review,发现写的不简洁不好的地方,帮忙指出,谢谢!

public class Solution {
    /**
     * @param A an integer array
     * @return  A list of integers includes the index of the first number and the index of the last number
     */
    public ArrayList<Integer> continuousSubarraySumII(int[] A) {
        // Write your code here
        ArrayList<Integer> ret = new ArrayList<Integer>();
        if (A == null){
            return ret;
        }
        ret.add(-1);
        ret.add(-1);
        int max = Integer.MIN_VALUE;
        int sum = 0;
        int start = 0;
        for(int i = 0; i < A.length; i++){
            sum += A【i】;
            if (sum > max){
                ret.set(0, start);
                ret.set(1, i);
                max = sum;
            }
            if(sum < 0 && i + 1 != A.length){
                start = i + 1;
                sum = 0;
            }
        }

        if (sum > 0) {
            for(int i = 0; i < start; i++){
                sum += A【i】;
                if(sum > max){
                    ret.set(0, start);
                    ret.set(1, i);
                    max = sum;
                }
                if(sum < 0){
                    break;
                }
            }
        }
        return ret;
    }
}


0

主题

0

精华

0

积分

新米人

Rank: 1

积分
0
发表于 6-18-2015 09:51 PM | 显示全部楼层
题目问的是rotated subarray, 如果找到的subarray不是rotated的应该是不对的

50

主题

1

精华

303

积分

高级会员

Rank: 3Rank: 3

积分
303
 楼主| 发表于 6-20-2015 10:39 AM | 显示全部楼层
LoveJecci 发表于 6-18-2015 09:51 PM
题目问的是rotated subarray, 如果找到的subarray不是rotated的应该是不对的

哦?是这个意思么?我后来发现哪里出错了,但不是这个原因。
是可以rotated,也可以不rotated的
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表