title: 5.2 数列 -nsum 问题 tags: [数列 -nsum 问题] ---## 5.2 数列 -nsum 问题 tag-placeholder

数组，找出和为 s 的两个数¶

暴力解法

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int res[] = new int[2];
        for(int i = 0; i < nums.length; i++){
            for(int j = i + 1; j < nums.length; j++){
                if(nums[i] + nums[j] == target){
                    res[0] = i;
                    res[1] = j;
                    break;
                }
            }
        }
        return res;
    }
}

使用 hash 表，2 遍扫描

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int res[] = new int[2];
        Map<Integer, Integer> map= new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            map.put(nums[i], i);
        }
        for(int i = 0; i < nums.length; i++){
            int temp = target - nums[i];
            if(map.containsKey(temp) && map.get(temp) != i){
                res[0] = map.get(temp);
                res[1] = i;
            }
        }
        return res;
    }
}

找出和为 N+1 的 2 个数¶

一个整数数列，元素取值可能是 1~N（N 是一个较大的正整数）中的任意一个数，相同数值不会重复出现。设计一个算法，找出数列中符合条件的数对的个数，满足数对中两数的和等于 N+1。复杂度最好是 O(n) ，如果是 O(n2) 则不得分。

分析：列出所有的数对,如输入 15，输出 【1，14】【2，13】【3，12】。。。

int print_sequence_sum(int n)

找出和为 m 的 2 个数¶

输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是 O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。例如输入数组【1、2、4、7、11、15=和数字 15。由于 4+11=15，因此输出 4 和 11。

//返回0找到，返回-1没找到
int findaddends(int *data,int length,int sum,int *a,int *b);

分析：数组升序排列，查找可用二分查找，时间复杂度 O(logn),这样问题就变成了找其中一个加数的问题，复杂度为 N*logN

巧妙解法：数组 2 端向中间扫描，复杂度 O(N)

求子数组的最大和 (最大字段和)¶

输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为 O(n)。

例如输入的数组为 1, -2, 3, 10, -4, 7, 2, -5 ，和最大的子数组为 3, 10, -4, 7, 2 ，因此输出为该子数组的和 18。

蛮力法 fmax(i,j) 找出最大的值，3 重循环，复杂度 0(n^3)
动态规划 maxendindhere 保存当前累加的和，如果<0, 就把 maxendinghere 清零， max 保存最终的最大和; 如果都是负数

    int maxSumOfVector(int *data,int length){

        int max=0;
        int maxendinghere = 0;

        if(data==NULL || length<=0){
            return 0;
        }
        for(int i=0;i < length, i++){

            maxendinghere+=data[i];
            if(maxendinghere<0){
                maxendinghere=0;
                continue;
            }

            if(maxendinghere>max){
                max=maxendinghere;
            }

        }

        return max;
    }

和为 n 连续正数序列¶

题目：输入一个正数 n，输出所有和为 n 连续正数序列。

例如输入 15，由于 1+2+3+4+5=4+5+6=7+8=15，所以输出 3 个连续序列 1-5、4-6 和 7-8。

print_continuous_sequence_sum(int n)

思路一：枚举法。从 1 开始一直加到等于 n，再从 2 开始。。一直到 n/2+1,在每一轮，都要逐步比较。复杂度 O（N^2） 思路二： a[small,big] sum[small,big]>N small 往前移动，否则，big 往前移动。 O（N） 复杂度搞定

求连续子数组和为 m 的组合¶

数组 [2,3,1,2,4,3] 求连续子数组 sum=7, 结果 [1,2,4] [3,4]

暴力遍历
滑动窗口, 左指针，右指针

if sum<k && r<len{
    sum+=arr[r]
    r++
}else{
    sum -= arr[l]
    l++
}

和为 m 的组合¶

编程求解：输入两个整数 n 和 m，从数列 1，2，3.......n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来.

如： n=10,m=25; 可能的组合有【】【】【】【】

print_sum_detials(int n , int sum)

动态规划（类似背包问题）

划分问题
选择状态
状态转移方程
规划方程

钞票面值 100,50,20,10,5,2,1 元，求支付 628 元最少需要几张钞票¶

思路：贪心算法

若干个数的和与 M 最为接近¶

给定一个实数数组，按序排列（从小到大）,从数组从找出若干个数，使得这若干个数的和与 M 最为接近，描述一个算法，并给出算法的复杂度。

数组分隔成和相等的 2 个子集¶

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等 (eetcode 416, 难度中等)

思路：动态规划

n 个骰子的点数¶

把 n 个骰子扔在地上，所有骰子朝上一面的点数之和为 S。输入 n，打印出 S 的所有可能的值出现的概率。

如 n=1，值 【1，2，3，4，5，6】 每个概率是 1/6 如 n=2，值 【1~12】 概率。。

一个整数数组，长度为 n，将其分为 m 份，使各份的和相等，求 m 的最大值¶

比如 {3，2，4，3，6} 可以分成 {3，2，4，3，6} m=1; {3,6}{2,4,3} m=2 {3,3}{2,4}{6} m=3 所以 m 的最大值为 3