[m.t]--算法-求数组中最接近0的子序列

拼搏现实的明天。 2022-07-10 13:28 140阅读 0赞

总结一下算法题。

> Question:求一个无序数组中最近接0的子序列。

\#1. 暴力算法：  
求最接近于0的子数组序列，那么数组中的任何一个元素都有可能成为这个子数组的起点，那么我们可以使用双重for循环求出以每个元素为开头的最接近0的子数组。其实就是两轮for循环，具体的算法就不给出了。

# 2. 优化算法： #

优化算法的主要步骤是：

> 1.  首先求出从0 到 i 的和sum\[i\];

1.  然后对sum\[\]进行排序,
2.  找出有序的sum\[\] 中相邻最小的差值的Node
3.  求出结果。

下面以序列\{-3, 1, 1, -3, 5\}为例做一个解释：

1）经过一次for循环我们将得到的nSum存入一个数组：  
【0（0），-3（1），-2（2），-1（3），-4（4）, 1（5）】  
![这里写图片描述][SouthEast]

2）然后对nSum数组进行排序，由于数组中每个元素存的是前i个元素的和，所以我们需要使用Arrays.sort()工具方法对其排序，并且自己实现的comparator，排序后结果如下：  
【-4（4），-3（1），-2（2），-1（3），0（0）, 1（5）】  
![这里写图片描述][SouthEast 1]

3）接下来再次迭代nSum数组，数组中的每个元素减去前一个元素，获取最小的差值组合。我们可以得出  
\-3（1） 减去 -4（4）为1，即为我们要找的最接近0的子序列。然后计算下标为1到3。

该算法的时间复杂度为O(nlogn), 其实也就是Arrays.sort()函数的时间复杂度。下面给出实现源码：

package algorithm;
    
    import java.util.Arrays;
    import java.util.Comparator;
    
    /** * Created by louyuting on 2017/2/17. */
    public class Test1 { 
    
        /** * 内部静类用于保存 数组序列中的前 i 项的和是sum */
        public static class Node{ 
            int sum;//前n项的和
            int index;
    
            public Node(int index, int sum){ 
                this.index = index;
                this.sum = sum;
            }
        }
    
        /** * 解决方案: * @param nums * @return */
        public static int[] subArrayMin(int[] nums){ 
            //1. 首先求出从0 到 i 的和sum[i];
            //2. 然后对sum[]进行排序,
            //3. 找出有序的sum[] 中相邻最小的差值的Node
            //4. 求出结果
    
            //鲁棒性
            if(nums==null || nums.length==0){ 
                return new int[]{ 0, 0};
            }
    
            //创建nums.length + 1 个元素的数组, 分别保存前0到前n 个元素的和
            Node[] nSum = new Node[nums.length+1];
            nSum[0] = new Node(0, 0);//前0项的和是0
            int preSum=0;//保存i-1想的和,计算优化使用.
    
            //保存前1到前n项的和
            for(int i=0; i<nums.length; i++){ 
                nSum[i+1] = new Node(i+1, preSum + nums[i]);
                preSum = nSum[i+1].sum;
            }
            //保存最近进0的数据
            int closest = Integer.MAX_VALUE;
    
            //将sum进行排序
            Arrays.sort(nSum, new Comparator<Node>() { 
                @Override
                public int compare(Node o1, Node o2) { 
                    return o1.sum-o2.sum;
                }
            });
    
            //保存下标结果
            int[] result = new int[2];
    
            //找出有序的sum[] 中相邻最小的差值的Node, 这里的差值肯定是非负的.
            for (int i = 1; i < nSum.length; i++){ 
                if (closest > (nSum[i].sum - nSum[i - 1].sum)){ 
                    closest = nSum[i].sum - nSum[i - 1].sum;
    
                    int[] temp = new int[]{ nSum[i].index - 1,  nSum[i - 1].index - 1};
                    Arrays.sort(temp);
                    result[0] = temp[0] + 1;
                    result[1] = temp[1];
                }
            }
            return result;
        }
    
        public static void main(String[] args) { 
            int[] ss = { -3, 1, 1, -3, 5};
    
            int[] res = subArrayMin(ss);
    
            System.out.println(res[0] + " " +res[1]);
        }
    }

[SouthEast]: /images/20220710/8b579193eb864f4cb06499eb555c1bb6.png
[SouthEast 1]: /images/20220710/0d0a2c23c70d4ea391637bd984d6ca93.png