Concise 100% approach and Mathematical proof
Motivation\nI prepare this post to show the trick which is frequently used in leetcode problems.\n\nAlgorithm\nFIrst of all, let us review the description. We a
**Motivation**\nI prepare this post to show the trick which is frequently used in leetcode problems.\n\n**Algorithm**\nFIrst of all, let us review the description. We assume the size of `nums` is `n`.\n* The array is already sorted s.t. `nums[i-1]<=nums[i]` as long as `0<=i-1<i<n`.\n* For each `0<=i<n`, we need to calculate `S[i]=D[i,0]+...+D[i,n-1]` which is the sum of `D[i,j]=abs(nums[i]-nums[j])` where `0<=j<n`.\n\t* ***Fact 1***: `D[i,j]=D[j,i]`\n\t* ***Fact 2***: `D[i,i-1]=D[i-1,i]=nums[i]-nums[i-1]`\n\t* ***Fact 3***: For `0<=j<=i`, `D[i,j]=abs(nums[i]-nums[j])=nums[i]-nums[j]`\n\t* ***Fact 4***: For `j>i`, `D[i,j]=abs(nums[i]-nums[j])=nums[j]-nums[i]`\n* Meanwhile, let us compare `S[i-1]` and `S[i]`\n\t* For `j` in `[0,i)`, `D[i-1,j]=abs(nums[i-1]-nums[j])=nums[i-1]-nums[j]` and `D[i,j]=abs(nums[i]-nums[j])=nums[i]-nums[j]`. Here, `D[i,j]-D[i-1,j]=D[i,i-1]` and the count of `[0,i)` is `i`\n\t* For `j` in `[i, n)`, `D[i-1,j]=abs(nums[i-1]-nums[j])=nums[j]-nums[i-1]` and `D[i,j]=abs(nums[i]-nums[i])=nums[j]-nums[i]`. Here, `D[i,j]-D[i-1,j]=-D[i,i-1]` and the count of `[i,n)` is `n-i`\n* Putting them together, `S[i]-S[i-1]=i*D[i,i-1]-(n-i)*D[i,i-1]=(i+i-n)*D[i,i-1]=(i+i-n)*(nums[i]-nums[i-1])`.\n\n**Review**\nFor many problems, we need to use similar strategy to simplify the calculation.\n\n**Complexity**\n```\nTime: O(n)\nRuntime: 53 ms, faster than 99.73% of C++ online submissions for Sum of Absolute Differences in a Sorted Array.\n\nSpace: O(1)\nMemory Usage: 83.8 MB, less than 60.81% of C++ online submissions for Sum of Absolute Differences in a Sorted Array.\n```\n\n**Codes**\n```\nclass Solution {\npublic:\n    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {\n        ios::sync_with_stdio(false);\n        cin.tie(nullptr);\n        int n=nums.size();\n        vector<int> ans(n);\n        for(int i=1; i<n; ans[0]+=nums[i++]-nums[0]) {}\n        for(int i=1; i<n; ++i) {\n            ans[i]=ans[i-1]+(i+i-n)*(nums[i]-nums[i-1]);\n        }        \n        return ans;\n    }\n};\n```
[]