题干

给定n个整数 a1,a2,⋯ ,an，求它们两两相乘再相加的和，即：

示例一：

输入：
4
1 3 6 9
输出：
117

题目链接：求和

解题思路一

初次看这个题目第一感觉是用两个双循环首先外循环的i从a1开始一直到an-1(n-1是下标)，内层循环从i+1开始一直到an，然后设置一个sum用于接收他们的和，如此一来就完成了求和，下面是完整代码：

代码

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        int[] arr = new int[num];
        int i = 0;
        while (num > 0) {
            arr[i] = scanner.nextInt();
            num--;
            i++;
        }
        int sum = 0;
        for (int n = 0; n < arr.length - 1; n++) {
            for (int m = n + 1; m < arr.length; m++) {
                sum = sum + arr[n] * arr[m];
            }
        }
        System.out.println(sum);
    }
}

这个方法很容易想到，但是我们发现了此方法的时间复杂度是O(n)，因此时间复杂度很大，如果用这个代码去提交我们就会发现并不能完全通过，因此需要找更简便的方法。

解题思路二

原题是：

提取公因式，我们可以化简为：

现在，我们要使用一种叫“前缀和”的方法，定义一个数组b，令bi=a1+a2+⋯+aj，很容易发现：

因此上述化简后的计算就可以化简为：

根据这个公式我们就能够完成求和，首先，我们创建另一个数组用于存储b，用一个for循环完成求和，下面是完整代码：

代码

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        long[] arr1 = new long[num];
        long[] arr2 = new long[num];
        int i = 0;
        while (num > 0) {
            arr1[i] = scanner.nextInt();
            num--;
            i++;
        }
        for (i = 0; i < arr2.length; i++) {
            if (i == 0) {
                arr2[i] = arr1[i];
            } else {
                arr2[i] = arr2[i - 1] + arr1[i];
            }
        }
        long sum = 0L;
        for (i = 0; i < arr1.length; i++) {
            sum = sum +arr1[i] * (arr2[arr2.length-1] - arr2[i]);
        }
        System.out.println(sum);
    }
}