蓝桥杯-求和问题
蓝桥杯-求和问题
1、问题描述
给定 n 个整数
，求它们两两相乘再相加的和，即：
输入格式
输入的第一行包含一个整数 n。
第二行包含 n 个整数
。
输出格式
输出一个整数 S，表示所求的和。请使用合适的数据类型进行运算。
样例输入
4
1 3 6 9样例输出
117评测用例规模与约定
对于 30% 的数据，1≤n≤1000,1≤ai≤100 。
对于所有测评用例，1≤n≤200000,1≤ai≤1000。
运行限制
- 最大运行时间：1s
- 最大运行内存: 512M
2、解法一：暴力解法(两层循环)
我们直接两个for循环就可以解决，每次遍历到某个数的额时候，让它与自己后面的所有数字相乘并求和即可。
以样例做个循环分析如下：
- i=0,j=1,2,3
- i=1,j=2,3
- i=2,j=3
代码如下：
// //暴力解法，这种会超时。
public static void sum1(){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] arr = new int[n];
long sum=0;
for (int i = 0; i < n; i++) {
int temp = scanner.nextInt();
arr[i]=temp;
}
for (int i = 0; i < arr.length; i++) {
for (int j =i+1; j <arr.length ; j++) {
sum+=arr[i]*arr[j];
}
}
System.out.println(sum);
scanner.close();
}运行结果如下：
这种会超时，看下面这种优化后的。
3、解法二：结合律(一层循环解决)
根据结合律化简求和公式如下所示：
如果输入为1 3 6 9
第一次两两相乘为1*3+1*6+1*9=1*(3+6+9)
第二次两两相乘为3*6+3*9=3*(+6+9)
第三次两两相乘为6*9=6*(9)
最后相加，即每一次该数乘以sum内不包含本身的值代码如下所示：
public static void sum2(){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] arr = new int[n];
long sum=0;
long result=0;
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
sum+=arr[i]; //直接刚开始就对数组求和
}
for (int i = 0; i <n; i++) {
sum=sum-arr[i];
result+=arr[i]*sum;
}
System.out.println(result);
}这里sum必须用long类型,要不会超出int范围
举报
腾讯云开发者
