买商品，买三送一，送价钱最低的，准备买n个商品（编号1-n），其中第i个商品的价格为Ai，现在找到策略，花最少的钱买到所有商品。
输入
第一行：一个整数n， 1<=n<=10,000
第二行：n个整数Ai，分别表示n个商品价格，1<=Ai<=1000,000
例：
输入：
4
100 200 300 400
输出：
800
一种方案：买 200 300 400 省200 ，再加100。

solution

import java.util.*;
public class test1 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
	//	sc.nextLine();
		long[] num=new long[n];
		for(int i=0;i<n;i++) {
			num[i]=sc.nextLong();
		long res=solution(num,n);
		System.out.println(res);
	private static long solution(long[] num, int n) {
		if(num==null || num.length==0) return 0;
		long sum=0;
		for(int i=0;i<n;i++) {
			sum+=num[i];
		if(n<3) return sum;
		else {
			Arrays.sort(num);
			int x=0;
			for(int i=n-1;i>=0;i--) {
				x++;
				if(x%3==0) {
					sum-=num[i];
			return sum;
记得要用 long ，写的时候先想好，然后再写省去不少代码，这个不用跳着for，直接判断如果能整除3，就减去就行，我自己的这个写的太复杂了
 先想好再写
 
1-n n个树，有和谐值Ai，如果一段连续的树，他们和谐值之和可以被m整除，那么这个 区间整体就是和谐的。求有多少个这样的区间的数量
 输入：
 第一行两个整数n、m
 第二行n个整数Ai，分别表示第i个数的和谐值
 0<=Ai<=1,000,000
 
输出：
 满足的数量
 
输入：
 5 2
 1 2 3 4 5
 输出
 6
 因为：
 【2】【4】
 【1 2 3】【3 4 5】
 【1 2 3 4】【2 3 4 5】
 
自己想了dp还是两个for循环
 暴力法两个for循环
 
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int[] nums = new int[n];
    for (int i = 0; i < n; i++) {
        nums[i] = sc.nextInt();
    sc.close();
    long res = 0;
    for (int i = 1; i <= n; i++) {
        long curr = 0;
        for (int j = 0; j < i; j++) {
            curr = curr + nums[j];
        if(curr % m == 0) res = res + 1;//找从头开始的总和整除的
        for (int k = i; k < n; k++) {//然后是1.2.3连续的组找
            curr = curr - nums[k - i] + nums[k];
            curr = curr % m;
            if(curr == 0) res = res + 1;
    System.out.println(res);
我的另一个方法：滑动窗口O（n…^2）
 
import java.util.Scanner;
public class test2 {
	static long count=0;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		long[] num=new long[n];
		for(int i=0;i<n;i++) {
			num[i]=sc.nextLong();
		long res=solution(n,num,m);
		System.out.println(res);
	private static long solution(int n, long[] num, int m) {
		if(num==null || n==0 || m<1) return 0;
	//	long count=0;
		for(int i=0;i<n;i++) {
			if(num[i]%m==0) count++;
		if(n==1) return count;
		for(int i=0;i<n;i++) {
			helper(num,i,m);
		return count;
	private static void helper(long[] num, int i, int m ) {
		int left=i,right=i+1;
		if(right>=num.length) return ;
		long sum=num[left]+num[right];
		while(left<right) {
			if(sum%m == 0) count++;
			if(right==num.length-1) break;
			if(right+1<num.length) {
				right++;
				sum+=num[right];
	//return count;
大神解法： 前缀和取模
 
leetcode 974
 974. 和可被 K 整除的子数组
 
哈希表（通过）
 思路：
 在方法一中我们利用前缀和数组来求解问题，对于子数组nums[i:j] (不包含下标j)，其区间和为sum[j] - sum[i] (其中sum 为预处理得到的前缀和数组),
 
我们要判断的是(sum[j] - sum[i])%K 是否等于0。
 根据modmod运算的性质，我们知道(sum[j] - sum[i])%K = =sum[j]%K−sum[i]%K。
 故若想(sum[j] - sum[i])%K = 0 ，则必有sum[j]%K = sum[i]%K。
 所有满足nums[i:j]nums[i:j]中元素之和可以被K整除的开始下标ii，必有sum[j]%K = sum[i]%Ksum[j]%K=sum[i]%K。我们以sum[i]%Ksum[i]%K作为键值统计其出现的频率，从而对于每个下标jj我们可以立即获得能和它组成满足要求的子数组的开始下标ii的数量。
 算法：
 生成前缀和数组的过程中，将key = sum[j]%kkey=sum[j]%k 出现的频率加入结果数组， 同时将 key = sum[j]%kkey=sum[j]%k的出现频率加11。
 由于数组中有可能出现负数，我们需要将其加KK从而使其%K%K之后的值为正数。
 
作者：KLEA
 链接：https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/solution/he-ke-bei-kzheng-chu-de-zi-shu-zu-by-lenn123/
 来源：力扣（LeetCode）
 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 
class Solution {
    public int subarraysDivByK(int[] A, int K) {
        int N = A.length, sum = 0, ans = 0;
        int[] map = new int[K];
        map[0] = 1;
        for (int i = 1; i <= N; i++) {
            sum = sum + A[i-1]; 
            int key = (sum % K + K) % K;
            ans += map[key];
            map[key]++;
        return ans;
作者：KLEA
链接：https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/solution/he-ke-bei-kzheng-chu-de-zi-shu-zu-by-lenn123/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
第三题 选靓号
 
给定字符串长度为N，字符串只会包括’0’-‘9’， 要求修改字符串使得至少有一个字符出现K次， 修改每个字符的代价为对应数字的变化大小，求最小代价，并输出最小代价下的最小字符串
 例如： 对于字符串 ‘787855’, K = 5， 则最小代价应该为4， 并且输出最小字符串’777757’（不能是’777775’， 因为不满足最小字符串）
 牛客原题
                                    【题目描述】
蛤布斯有n种商品，第i种物品的价格为ai，价值为bi。有m个人来向蛤布斯购买商品，每个人每种物品只能购买一个。第j个人有cj的钱，他会不停选择一个能买得起的价格最高的商品买走（如果有多个则选择价值最高的）。你需要求出每个人购买的物品的价值和。
【输入数据】
      第一行两个正整数n，m。接下来n行每行两个正整数ai，bi。接下来m行每行一个正整数cj。
【输出数据】
没记错的话12道单选，6道多选，4道填空，4道问答
问答1.编程题：找出字母列"AABBCAZDFEH"中重复的字母并按顺序输出
思考：对每个待处理的字符，假设为c，将c与s中的第0—(l-1)个字符相比较，如果有相同的，则处理c后面的一个字符；如果没有相同的，就将c存放到s的第l个位置上，然后在处理c后面的一个字符。
void deleteRepea...
                                    选择、填空题：1.IP地址，子网掩码的计算2.Internet网络层重要协议3.http请求方法4.HTML中a标签的伪类5.alert(undefined==null)的输出结果6.http和https协议7.flex-direction设置属性8.var a=[];a[0]=1,a[1]=2,a[2]=3,a[5]=4;a.length = ?9.JS判断数据类型的方法10.跨域资源共享COR...
给出长虔都为n的两个整数数组a[n]和b[n]，特殊运算 S = a[0]*b[0] + ... + a[n-1]*b[n-1]，你可以改变a数组的顺序使得运算S得到的值最小，给出最终的最小值。
数组长度n大于50，对于每个元素X，0&l...
                                    4月3号做了拼多多笔试题。先把题目在下面表述出来，方便读者自己尝试。下面说明自己的思路和贴上代码。因为是凭记忆，所以和题目叙述可能不同，但是意思肯定一样。4道题时间统一都是C/C++ 1秒其他2秒
第一题：两两配对差值最小。有n（n为偶数）个数，将之两两配对之后求和，得到的n/2个和中最大值和最小值的差值为value，问value的最小值是多少。输入说明：第一行为数的个数n，第二行为空格隔开的n...
                                    在经过了腾讯的洗礼后，这次拼多多的笔试做的还不错。2个小时4道编程题，都做对了。在此凭记忆写下题目并给出解答。
第一题：给一组数，数的个数是偶数，两两配对求和，使得和的最大值减去和的最小值最小。求这个差值。
题目看上去挺难的，当时想了一下感觉就是排序后第一个和最后一个组合，第二个和倒数第二个组合……记录一下最大值和最小值就行了。后来提交上去AC了。改天用数学证明一下这种配对方式是使得最小差值的...
                                    三轮面试，两轮技术面，一轮HR面第一轮技术面：1 问了一下自己的项目，虽然是硬件项目和自己面试的职位没有任何关系，但面试官还是提了几个认真的问题：元器件怎么选型的之类的。2 面试官问了自己什么时候开始学编程的，都看了什么资料。3 C++里面你常用的数据结构有哪些？详细介绍一下。4 tcp三次握手过程描述一下。5 手写代码，给定二叉树根节点，和一个value值，求从根节点到叶子节点路径上所有节点值之...