查找数列中数的位置

Question

有一列数组

• 全部为正整数或 0
• 数组中可以有相同的数

求解
给定一个数在小于数组总和大于等于 0 之间的正整数，
求从数组 0开始向后依次相加，根据相加的值与给定的数进行比较，
当相加值大于或等于给定数的差距最小时,返回当前相加的最后一位

如:
[0,1,90,30,67,30,2,4,5,610,34,0] 总和：873 长度：11

给定的数：30 返回数组索引 2
因为 (0 + 1 + 90) > 30 这个最小的大于值

给定的数：122 返回数组索引 4
因为 (0 + 1 + 90 + 30 +67) > 122 这个最小的大于值

给定的数：0 返回数组索引 0
因为 0 = 0 这个最小的等于值 （当为 0 时 只有索引 0 满足条件 所以可以直接返回 0）

想知道有没有时间复杂度与空间复杂度较优的JavaScript | TypeScript | Rust 解

Answer 1

这道题不难啊，因为限定很多的,特别是给的数是[0,数组和]内的，而且所有数都是非负数，则直接累加比较加终止条件就好

let a=[0,1,90,30,67,30,2,4,5,610,34,0]
function getIdx(x,arr){
    let i=0;
    let sum=0;
    let len=arr.length;
    for(;i<len;i++){
        sum=sum+arr[i];
        if(sum>=x) break;
    }
    return i; // 这样是算法判断不了是否出错，其实稍微处理一下，如果x大于数组和，则返回-1也是可以的，比如 
    //return ( (sum>=x)?i:-1);
}
console.log( getIdx( 30,a) );
console.log( getIdx( 122,a) );
console.log( getIdx( 0,a) );
console.log( getIdx(873,a) );

因为这个方案复杂度已经是O(n)的啦，基本没有太多优化空间啊，毕竟就是数组求1次和也需要O(n)啊。